#숫자 N까지 소수 개수 구하는 함수
def isPrimeBelow(N):
sieve = [1] * (N+1)
sieve[0] = 0
sieve[1] = 0
for i in range(2, int(N**0.5)+1):
if sieve[i] == 1:
for j in range(i+i, N+1, i):
sieve[j] = 0
return sieve
#가장 큰 숫자까지 미리 소수를 구해놓기
prime_list = isPrimeBelow(246913)
for i in range(123457):
N = int(input())
if N == 0: break
print(prime_list[N+1:2*N+1].count(1))
## Comment1 : 여러 숫자에 대해 Input을 받으므로 처음부터 소수 전체 List를 작성하는 것이 Point! 이전 문제와 같이 input 받은 숫자 대로 소수 판별 함수에 넣고 돌리면 시간 초과가 뜬다.
## Comment2 : 함수를 사용하는 것은 좋으나 이것이 여러번 호출되지는 않는지 확인이 필요하다
'백준's 단계별 풀이' 카테고리의 다른 글
Stage_9 (기본수학2) 9020번 골드바흐의 추측 (0) | 2021.04.15 |
---|---|
Stage_9 (기본수학2) 192번 소인수분해 (0) | 2021.04.06 |
Stage_9 (기본수학2) 11653번 소인수분해 (0) | 2021.04.06 |
Stage_8 (기본수학2) 2581번 소수 (0) | 2021.03.30 |
Stage_8 (기본수학2) 1978번 소수 찾기 (0) | 2021.03.23 |