[Python] 소수(에라토스테네스 체)

[문제]

소수(에라토스테네스 체)
자연수 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

---

[풀이]

import sys

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)

---

[중요내용]

1. ch 리스트의 인덱스 값을 해당 숫자라고 생각하지 못했었음

2. 1은 소수가 아니기 때문에 for문의 시작을 2부터 해야했었음 => 1부터 돌린 다음에 1을 추가시켜서 안됐었음!

3. '에라토스테네스의 체' 를 몰랐었음

- 소수 자신을 제외한 소수의 배수들 (3이 소수라면 그 배수인 3, 6, 9...) 은 3을 약수로 갖고 있는 숫자들이므로 당연히 3으로 나누어진다(=소수가 아니다) 라는 사실을 이용하는 방법이다.

4. range(start, end, start): start의 배수만 선택해서 접근 가능