[파이썬] 소수의 개수(에라토스테네스 체)

문제

• 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램

풀이

• 에라토스테네스 체를 이용하면 빠르게 구할 수 있다.

N=20
cnt = 0
ch = [0]*(N+1)
for i in range(2, N+1):
    if ch[i] == 0:
        cnt +=1
        for j in range(i, N+1, i):
            ch[j]=1

print(cnt)

• 에라토스테네스의 체 란?

  2, 3, 5, 7의 배수를 지워서 소수만 남기는 방법.

  반복문을 줄여서 시간을 단축