[python] 코딩테스트 대비 - 소수(에라토스테네스 체)

문제)

 

import sys
#sys.stdin=open("input.txt","rt")
#숫자마다 2부터 시작해서 소수를 체크하는 방식은 시간초과가 발생함.
N=int(input())
 
check=[0]*(N+1)#총 n+1개의 리스트 (인덱스3은 숫자3을 의미)
count=0
for i in range(2,N+1):#인덱스 2부터(0 1은 확인할 필요 없음,) N까지 반복
    if check[i]==0:#i인덱스가 소수라면
        count+=1#카운트 증가
        for j in range(i,N+1,i):#i의 배수들은 소수가 아님을 표시
            check[j]=1
print(count)