# 백준BOJ/Python : 1929번 소수 구하기

- Author: @laetipark
- Published: 2023-04-17
- Updated: 2023-05-23
- Source: http://blex.me/@laetipark/%EB%B0%B1%EC%A4%80bojpython-1929%EB%B2%88-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0
- Tags: python, algorithm, 백준, boj, baekjoon, 에라토스테네스의체, 소수

---

[1929번 : 소수 구하기 원본](https://www.acmicpc.net/problem/1929)

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

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

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

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

### 풀이
소수 : 1보다 큰 자연수 중 1과 자기 자신으로만 나눠지는 수
에라토스테네스의 체 : 에라토스테네스가 발견한 소수 찾는 방법
@gif[https://static.blex.me/images/content/2023/4/17/202341722_ziTKAcQgUjDtgJw1z5g8.mp4]
1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열
2. 2는 소수이므로 2를 넣고, 2를 제외한 2의 배수를 모두 지움
3. 남아있는 수 중 3도 소수이므로 3을 소수에 넣고 3을 제외한 3의 배수를 모두 지움
4. 3 과정을 반복하면 원하는 구간의 소수를 찾을 수 있음
5. 2부터 120까지 소수를 구할 경우 120보다 큰 수의 제곱근을 갖는 자연수는 11(11^2 = 121)이므로, 11보다 작은 자연수까지 과정을 반복하면 됨

### 소스 코드
##### Python 1
- 에라토스테네스의 체 방식을 이용한 소수 구하기
- 전체를 구하는 방식 O(N)
```python
import sys

input = sys.stdin.readline
minNum, maxNum = map(int, input().split())
ListNum = [True] * (maxNum+1)
ListNum[0] = False
ListNum[1] = False

for i in range(2, int(maxNum**0.5) + 1):
    if ListNum[i]:
        for j in range(i*2, maxNum+1, i):
            ListNum[j] = False

for i in range(minNum, maxNum+1):
    if ListNum[i]:
        print(i)
```

##### Python 2
- 약수가 존재 여부를 확인해 소수를 찾는 방법
```python
import math
import sys

input = sys.stdin.readline

def is_prime(parse_int):
    if parse_int == 1:
        return False

    sqrt = int(math.sqrt(parse_int))

    for i in range(2, sqrt+1):
        if parse_int % i == 0:
            return False

    return True

min_num, max_num = map(int, input().split())

for i in range(min_num, max_num+1):
    if is_prime(i) == True:
        print(i)
```

### 참고
[에라토스테네스의 체, 위키백과](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)