[Math] 4948번 - 베르트랑 공준(50일차)

#코드 실행 시간 단축
import sys
input = sys.stdin.readline

#범위 내 소수 선택 및 count
def sosu(n):
    #범위 내 소수를 세는 변수
    sosu_cnt = 0
    #범위 내 소수를 선택해서 저장하는 list
    sosu_list = [True]*((2*n)+1)

    #2부터 2n 범위까지 소수 생성
    for i in range(2,(2*n)+1):
        #해당 숫자가 소수라면
        if(sosu_list[i] == True):
            #해당숫자를 기준으로 범위 내 배수들을 비소수로 설정
            for j in range(2*i,(2*n)+1, i):
                sosu_list[j] = False
            #소수가 범위 내에 있을 때 count
            if(n < i <= 2*n):
                sosu_cnt += 1

    #범위 내 소수 개수 세기
    return sosu_cnt

#무한반복
while(True):
    #숫자 입력
    N = int(input())

    #0이면 루프 탈출
    if(N == 0):
        break

    #0이 아니면 n~2n 범위 내 소수 count
    else:
        print(sosu(N))

#인사이트
#메모리 소모와 시간복잡도를 신경쓰는 for문 및 변수 설계가 중요