백준 #4948: 베르트랑 공준

 

접근법

---

소수 시리즈 4탄이다. 어벤저스도 4편이 엔드게임인데 소수도 이제 엔드게임이었으면 좋겠다.

 

이번 문제도 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다.

 

에라토스테네스의 체에 대한 자세한 설명은 이전 포스팅에 있으니 참고바란다. (이전 포스팅)

 

우선 숫자 0이 들어올 때까지 해당 프로그램은 무한루프를 돌아야 한다. 그리고 각 케이스 별로 입력값이 주어지면

 

입력값의 두배에 해당하는 범위까지의 소수의 개수를 찾아야한다.

 

따라서, 이전에 만들어 두었던 프로그램을 활용하면 손쉽게 문제를 풀 수 있다.

 

 

풀이

---

while True:
    n = int(input())
    N = 2 * n
    if n == 0 :
        break
    else :
        arr = [i for i in range(N+1)]
        arr[1] = 0
        for i in range(2,N+1):
            if arr[i] == 0:
                continue
            for j in range(i*2,N+1,i):
                arr[j] = 0
        prime = [i for i in range(n+1,N+1) if arr[i] == i]
        print(len(prime))

 

 

문제 출처 : 백준