소수(에라토스테네스 체)

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.

▣ 입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

▣ 출력설명
첫 줄에 소수의 개수를 출력합니다.

▣ 입력예제 1
20

▣ 출력예제 1
8

---

접근법

인덱스 번호중 소수가 누구인지 체크하며 확인하기

 

 

체크가 안되어 있으면 카운팅을 해준다.
2의 배수를 체크하면서 걸러낸다. 1을 넣어줌으로써

체크가 안되어 있으면 카운팅을 해준다.
3의 배수를 체크하면서 걸러낸다. 1을 넣어줌으로써

---

코드

N = int(input())

array = [0]*(N+1)
count = 0

for i in range(2, N+1): # 2부터 체크
    if array[i] == 0:
        count += 1
        for j in range(i, N+1, i): # i의 배수들 체크 (스타트, 엔드, 배수만큼 증가)
            array[j] = 1
print(count)