초이의 끄적끄적

단계별풀기 - 기본수학2

# 4948 베르트랑 공준 (실버2)

• 각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.
• point. 시간초과 에라토스테네스의 체 사용해서 소수 구하기

def isprime(m, n):
    count = 0
    prime = [True] * n  # n개의 [True]가 있는 리스트 생성
    for i in range(2, int(n ** 0.5) + 1):  # n의 제곱근까지만 검사
        if prime[i]:  # prime[i]가 True일때
            for j in range(2 * i, n, i):  # prime 내 i의 배수들을 False로 변환
                prime[j] = False

    for i in range(m, n):
        if i > 1 and prime[i] == True:  # 1 이상이면서 남은 소수들을 출력
            count+=1
    return count

while True:
    n = int(input())
    n_count = 0
    if n==0:
        break
    print(isprime(n+1,n*2+1)) # n< <=2n