# [til] 알고리즘 백준 1929

### 📌 오늘의 알고리즘 문제 (소수 구하기)

#### 🚩 문제 설명

백준 1929번: [https://www.acmicpc.net/problem/1929](https://www.acmicpc.net/problem/1929)

주어진 자연수 M 이상 N 이하의 소수를 모두 출력하는 문제다.

#### 📖 풀이 전략

* 특정 숫자가 소수인지 확인하는 간단한 알고리즘을 사용했다.
    
* 2부터 그 숫자의 제곱근까지만 나누어보며 나누어떨어지면 소수가 아니다.
    
* 입력 범위 내 모든 수에 대해 위 과정을 반복했다.
    

#### 💡 핵심 포인트

* **소수 판별의 효율성**
    
    * 숫자 x가 소수인지 확인할 때 x의 제곱근까지만 확인하면 된다.
        
    * 이유: 약수가 존재한다면 무조건 제곱근 이하에 존재하기 때문이다.
        

#### 🛠️ 사용한 알고리즘 및 함수

* 소수 판별 함수 `is_prime()`
    
* ```python
    def is_prime(x):
        if x == 1:
            return False
        for i in range(2, int(math.sqrt(x) + 1)):
            if x % i == 0:
                return False
        return True
    ```
    

#### 📌 배운 점

* 소수를 효율적으로 판별할 때는 제곱근까지만 반복하면 충분하다.
    
* 범위 내에서 여러 소수를 출력하는 경우, 반복문과 소수 판별 함수를 분리해 가독성을 높일 수 있다.
    

💻**문제풀이 전체코드**

```python
import sys
import math


def is_prime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x) + 1)):
        if x % i == 0:
            return False
    return True


m, n = map(int, sys.stdin.readline().split())

for i in range(m, n + 1):
    if is_prime(i):
        print(i)
```