[python/inflearn/section2] 소수(에라토스테네스 체)

본 내용은 파이썬 알고리즘 문제풀이 (코딩테스트 대비) 강의를 토대로 작성하였습니다.

이미지 클릭시, 강의로 이동됩니닷 :)

# 소수의개수
import sys
sys.stdin=open("input.txt", "r")
n=int(input())
ch=[0]*(n+1)
# 소수의개수
cnt=0
for i in range(2, n+1):
    # 소수라면
    if ch[i]==0:
        cnt+=1
        # 배수들모두 1로 
        for j in range(i, n+1, i):
            ch[j]=1
print(cnt)