에라토스테네스 체

소수의 개수를 구하는 방법이다

일단 자연수의 개수만큼의 길이를 가진 리스트를 생성한다

for i는 2부터 n까지
array[2]가 0이면 1으로 올리고,
index가 2의 배수인 곳을 모두 1씩 증가시킨다.
-> 소수가 아닌 것으로 필터링 시키기!

array[3] == 0 이기 때문에 소수! 1으로 증가시키고,
3의 배수인 곳을 모두 1로 증가시켜 필터링 시키기

array[4] != 0 이므로 1으로 증가시킬 필요도 없고,
이미 배수도 1로 증가되어 있기 때문에 그 다음 for문도 실행시킬 필요가 없다

반복하기~~

코드로 구현하면 다음과 같다

n = int(input())
ch = [0] * (n + 1)
cnt = 0
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)