[백준,Python] 1929. 소수 구하기(feat.에라토스테네스의 체)

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

 

해설:

 

처음에는 무식하게 1과 자기 자신을 제외한 수로 일일이 나눠서 소수를 구했지만

 

"시간 초과"

 

그래서 인터넷을 좀 뒤져 봤더니 "에라토스테네스의 체"라는 방법을 찾았다!

 

(이름이 일단 좀 간지난다.. 아는 척하면 좀 있어 보일 수도?)

 

 

-근엄-

 

 

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

 

 

설명은 이걸 찾아봐라.

 

 

 

 

 

1. 내가 직접 푼 답안

 

 

M, N = map(int, input().split())
prime_list = [1] * (N - M + 1)
if M == 1:
    prime_list[0] = 0
for i in range(2, int(math.sqrt(N)) + 1):
    j = 2
    while i * j - M < len(prime_list):
        if i * j >= M:
            prime_list[i * j - M] = 0
        j += 1
 
for i, temp in enumerate(prime_list):
    if temp == 1:
        print(i + M)

 

해설:

 

길이가 N-M+1이고 1로 채워진 리스트를 생성한다.

리스트의 시작 인덱스인 0을 M이라 생각하자.

(그래서 코드가 얼핏 보면 이해가 잘 안된다)

그 후 에라토스테네스의 체를 이용하여 소수가 아닌 수를 0으로 채워나간다.

 

 

 

 

 

2. 이해하기 좀 더 나은 코드

 

 

M, N = map(int, input().split())
# 인덱스를 계산하기 편하게 맞춤
prime_list = [False] * M + [True] * (N - M + 1)
if M == 1:
    prime_list[1] = False
for i in range(2,int(math.sqrt(N)) + 1):
    j = 2
    while i * j <= N:
        prime_list[i * j] = False
        j += 1
 
for i, bool in enumerate(prime_list):
    if bool == True:
        print(i)

 

해설:

 

1번의 코드는 인덱스를 이해하기가 조금 어려웠는데

이번 코드는 메모리는 좀 더 쓰더라도 코드가 직관적이다.