[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
sys.stdin=open('H:/Study/CodingTest_Python/input.txt', 'rt')

n = int(input())
n_list = [0]*(n+1) #n_list[0] 에서 n_list[21] 까지 있는 리스트 생성 
cnt = 0

for i in range(2, n+1): #2에서 20까지
    if n_list[i] == 0: #n_list[2] 2가 0이면
        cnt += 1
        for j in range(i, n+1, i): #2의배수(n_list[2], [4], [6]...)
            n_list[j] = 1

print(cnt)

풀이 설명:
- n_list = [0]*(n+1) : n_list[0] 에서 n_list[n] 까지 있는 리스트 생성한다. 여기서 인덱스 값이 입력값 각각을 의미한다.
                          예를 들어, 입력값이 20이면 0에서 20까지의 리스트를 만든다고 생각하면 된다. 

- for i in range(2, n+1):  어차피 소수는 2부터니까 반복문을 2에서 입력값 까지 도는것으로 설정한다. 

- if n_list[i] == 0: 
        cnt += 1  : n_list[i]값이 0이면 카운트를 1씩 증가한다.
                       기본값을 0으로 설정했으므로 처음값인 n_list[2]는 카운트가된다.

- for j in range(i, n+1, i): 
            n_list[j] = 1  : i가 2라면 2의배수에 해당하는 인덱스는 모두 1이되고 3이라면
                              3의 배수에 해당하는 인덱스 모두 1이된다.