문제 / 소수 개수 출력하기 (에라토스테네스 체) / Python

 

문제 제목: 소수 개수 출력하기 (에라토스테네스 체)

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

제한시간은 1초입니다.

 

▣ 입력설명

 

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

 

▣ 출력설명

 

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

 

▣ 입력예제 

 

20

 

▣ 출력예제 

 

8

 

 

---

풀이

n = int(input())
sosu = [0]*(n+1)
cnt = 0

for  i in range(2,n+1):
    if sosu[i] == 0: 
        cnt += 1 #소수의 개수

    for j in range(i,n+1,i): #i의 배수는 1을 저장 (에라토스테네스 체)
        sosu[j] = 1
        

print(cnt)

 

*에라토스테네스의 체:

리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

 

[네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과 두피디아, 두산백과)

 

위의 풀이는 배수에 1을 저장하여 소수는 0을 가진 값을 출력하는 방식으로 에라토스테네스의 체를 이용하였다.

 

---

※ 알아야 할 것

- 소수를 찾으려면 자연수의 배수를 지워나가면 된다.