📢 문제

백준 문제 링크

🔎 풀이

사용 언어 : python
n과 2n까지의 소수를 판별하는 코드를 while문 안에 넣으면 시간초과 문제 발생

1 <= n <= 123456이므로
2*(123456) 까지 에라토스테네스의 체를 이용하여 소수를 미리 판별한 후
while문에서 n부터 2n까지의 소수의 개수를 구한다.

🔎 코드

# 이 코드를 while문 안에 넣으면 시간초과기 된다.
result = [True] * (2 * 123456 + 1)
result[1] = False
for i in range(2, 2*123456 + 1):
    if result[i]:
        a = 2
        while i * a <= 2*123456:
            result[i * a] = False
            a += 1

while 1:
    n = int(input())
    if n == 0:
        break
    count = 0

    for z in range(n+1, 2*n+1):
        if result[z] == True:
            count += 1
    print(count)