백준 1929번 파이썬 풀이: 소수 구하기

백준 1929번 소수 구하기

 

알고리즘 분류: 수학, 정수론, 소수 판정, 에라토스테네스의 체

 

링크: https://www.acmicpc.net/problem/1929

 

1929번: 소수 구하기

문제

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

입력

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

출력

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

 

문제 파악

 

백준 2581번 파이썬 풀이: 소수

앞서 풀어보았던 이 문제와 같은 문제이다.

 

그러나 입력값이 100만 까지 주어질 수 있으므로 이것보다 더 효율적인 코드를 작성해야

 

시간초과에 걸리지 않을 것이다.

 

문제에 한 가지 힌트가 들어있다면 알고리즘 분류에 에라토스테네스의 체가 들어있다는 것인데

 

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체란 소수를 찾는 알고리즘 중 하나인데

 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11² > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.

 

즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

 

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

코드

# 1929번

m, n = map(int, input().split())

prime_list = [True] * (n + 1)
x = int((n + 1) ** 0.5)

for i in range(2, x + 1):
    if prime_list[i] == True:
        for j in range(i + i, n + 1, i):
            prime_list[j] = False


sieve = [i for i in range(2, n + 1) if prime_list[i] == True]

for i in range(len(sieve)):
    if sieve[i] >= m:
        print(sieve[i])

이 알고리즘의 핵심은 (어떤 수)² < n < (어떤 수 + 1)² 이라고 했을 때

 

(어떤 수 + 1) 보다 작은 소수들의 배수들만 지워도 소수만 남는다는 것이다.

 

일단 prime_list를 n + 1 길이를 갖고 모든 요소를 소수로 간주하기 위해 True를 설정해둔다.

 

x는 앞서 말했듯이 어떤 수 보다 작은 소수들의 배수를 지우기 위한 어떤 수이다.

 

반복문을 통해 i가 소수라면 i의 배수들은 소수가 아니기 때문에

 

x + 1보다 작은 소수들의 배수를 다 False로 바꿔준다.

 

이렇게해서 걸러낸 소수들의 리스트를 sieve라는 리스트에 담아준다.

# 1번 방법
sieve = [i for i in range(2, n + 1) if prime_list[i] == True]

# 둘이 같음

# 2번 방법
sieve = []
for i in range(2, n + 1):
    if prime_list[i] == True:
        sieve.append(i)

for문과 if문을 한번에 쓰는 문법이 어렵다면 둘이 같은 말이기 때문에 2번 방법을 이용하면 된다.

 

이렇게 하면 sieve에는 n까지의 소수 목록들이 들어가있는데

 

이 중에서 m이상 n이하의 소수들을 모두 출력해야 하기 때문에

 

sieve의 요소 중에서 m보다 크거나 같은 수들만 출력해주면 된다.