[Algorithms] Basic-소수(에라토스테네스 체)

• 에라토스테네스 체 : 소수를 찾는 방법
• 숫자들을 배열해 놓고 배수가 되는 수들을 지워나가는 방법이 마치 체로 걸러내는 것 같다고 하여 에라토스테네스 체 라고 불린다

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

• 문제풀이에서는 소수인지 아닌지 체크하는 체크리스트 배열 하나를 만들어서 진행한다

import sys
 
sys.stdin = open("input", "rt")
n = int(input())
 
check_ls = [0]*(n+1)        //소수인지 아닌지 판별하기 위한 체크리스트 배열
cnt = 0
for i in range(2, n+1):
    if check_ls[i] == 0:    //0이라면 소수이므로 통과해서
        cnt += 1            //cnt를 올려주고
        for j in range(i, n+1, i):    //그 소수의 배수에 해당하는 수들을 
            check_ls[j]=1            //체크리스트에서 1로 변경해준다
print(cnt)