[파이썬] 백준 1929 소수 구하기, 소수 판별법

✅ 백준 문제 링크: 백준 1929번 - 소수 구하기

백준 1929

1. 소수란?

 

소수(Prime Number)란 1과 자기 자신으로만 나누어 떨어지는 수를 의미합니다.

즉, 약수가 1과 자기 자신뿐인 수를 소수라고 합니다.

 

✅ 소수 예시 (1~10까지)

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 → 소수: 2, 3, 5, 7

 

2. 소수 판별법

 

어떤 수 N이 소수인지 판별하는 기본적인 방법은

1부터 N까지의 모든 수로 나누어보는 것이다.

 

그러나 이 방법은 시간 복잡도가 O(N) 이므로,

입력값이 커질 경우 비효율적이다.

 

✅ 최적화된 소수 판별법 (제곱근 이용)

 

어떤 수 N이 소수인지 판별할 때,

“N의 제곱근 이하의 수까지만 나누어 보면 충분” 하다.

즉, sqrt(N) 이하의 수까지만 나눠보고 나누어 떨어지지 않으면 소수이다.

 

✔ Python에서는 math.sqrt() 함수를 사용하여 제곱근을 구할 수 있다.

 

3. 시간 초과 발생하는 비효율적인 코드

 

아래는 입력값 기반의 반복문으로 모든 수를 나누어 보는 방식이다.

이 방식은 O(N^2)에 가까운 시간 복잡도를 가지며,

백준 문제에서 시간 초과(Time Limit Exceeded, TLE) 가 발생한다.

#입력값 기반의 반복문으로는 시간초과 발생
import sys
var = sys.stdin.readline().rstrip().split(" ")
rtn = ""
for i in range(int(var[0]), int(var[1])+1):
    pnumYN = ""
    cnt = 2
    while cnt <= i:
        if (i!=cnt and i%cnt == 0):            
            break # 합성수이면 종료
        elif (cnt == i):
            rtn += str(i)+"\n" # 소수이면 결과 추가
        cnt += 1
print(rtn.rstrip())

✔ 위 코드는 O(N^2)에 가까운 시간 복잡도를 가지므로 비효율적이다.

 

4. 최적화된 소수 판별 코드 (제곱근 활용)

 

위 코드의 비효율적인 부분을 개선하여,

“N의 제곱근 이하의 수까지만 나눠보는 방법” 을 적용한다.

 

✔ math 모듈의 sqrt() 함수를 사용하여 제곱근을 구한다.

✔ 불필요한 반복을 줄여 실행 시간을 단축한다.

#입력값 받기
import sys
import math
M, N = sys.stdin.readline().rstrip().split(" ")

#어떤 수 N의 양의 제곱근 이하의 수들로 N을 나눠서 한 번이라도 나누어 떨어지면 합성수, 아니면 소수라고 판정
def primeNumYN(num):    
    if num == 1:
        return "N"
    if num == 2:
        return "Y"
    if (num % 2 == 0):
        return "N" # 짝수는 소수가 아님
    if (num > 2):
		#num 의 제곱근 이하까지 반복 (math.sqrt() 사용)
        # 3부터 sqrt(num)까지 홀수만 체크
        for i in range(3, math.trunc(math.sqrt(float(num)))+1, 2):
            if (num % i == 0):
                return "N"
        return "Y"
        
# M부터 N까지 소수 찾기
for j in range(int(M), int(N)+1):
    if (primeNumYN(j) == "Y"):
        print(j)

 

5. 예제 테스트

 

✔ 입력 예시 1

3 16

 

✔ 출력 예시 1

3
5
7
11
13

 

✔ 입력 예시 2

10 50

 

✔ 출력 예시 2

11
13
17
19
23
29
31
37
41
43
47

 

6. 소수 판별 알고리즘 성능 비교

방법	시간 복잡도	비고
1부터 N까지 모든 수를 나누어 보기	O(N^2)	시간 초과 발생
제곱근을 이용한 최적화	O(N log log N)	빠름 (에라토스테네스의 체보다 느림)
에라토스테네스의 체	O(N log log N)	가장 빠른 방법

✔ 제곱근을 이용한 방법은 대부분의 문제에서 통과가 가능하지만, 더 빠른 알고리즘(에라토스테네스의 체)이 존재한다.

✔ 소수를 대량으로 찾아야 할 경우, “에라토스테네스의 체”를 사용하면 더욱 빠른 성능을 얻을 수 있다.

 

7. 결론

 

✔ 소수 판별 시, “제곱근 이하의 수까지만 나눠보는 방법”을 사용하면 시간 복잡도를 줄일 수 있다.

✔ 백준 1929번 문제에서는 math.sqrt() 함수를 이용하여 O(N log log N)으로 해결할 수 있다.

✔ 더 빠른 방법이 필요한 경우, “에라토스테네스의 체”를 적용하면 더욱 효율적이다.