[BOJ]1929 - 소수 구하기

 

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

 

 

코드

import sys

M, N = map(int, sys.stdin.readline().split())
prime_num = []

for i in range(M, N+1):
    condition = True
    if i == 1:
    	continue
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)

print(*prime_num, sep='\n')

 

처음 코드를 작성할 때 소수를 판별하는 조건을 작성하는데 꽤 머리를 썼습니다.

 

코드를 보면 j를 2부터 √i까지 반복하면서 i가 소수인지 확인하는 코드 부분을 짤 때 생각했던 것입니다.

---

1. 소수의 정의

소수(Prime Number)란, 1과 자기 자신을 제외한 다른 수로 나누어떨어지지 않는 수다.

---

2. 소수를 판별하는 일반적인 방법

어떤 수 i가 소수인지 판별하려면 1부터 i-1까지 나누어떨어지는지 확인하면 된다. 하지만, 이렇게 하면 너무 비효율적. 알고리즘 문제는 이게 목적이 아니다.

 

예를 들어, 100이 소수인지 판별하려면?

• 2,3,4,5, ..., 99까지 다 나눠볼 필요가 있나?
• 없다. 사실 2부터 10까지만 검사하면 충분하다. (여기서 10=√100)

---

3. √i까지만 검사하면 되는 이유

어떤 수 i가 소수가 아니라면, i는 반드시 두 개의 자연수의 곱으로 나타낼 수 있다. 즉, i = a x b

 

여기서 a와 b는 1과 i가 아닌 자연수다.

이제 중요한 점은 a와 b 중 적어도 하나는 √i 이하다.

 

예제 1: 100의 약수 쌍

100 = 2 × 50
100 = 4 × 25
100 = 5 × 20
100 = 10 × 10 <-- 여기까지 보면 됨!
100 = 20 × 5
100 = 25 × 4
100 = 50 × 2

 

약수 쌍을 보면 10 × 10을 기준으로 대칭적이다.

즉, 10보다 큰 약수를 확인할 필요가 없다.
왜냐하면 20이 100의 약수인지 확인하는 순간, 이미 5도 약수라는 걸 알 수 있기 때문이다.

 

이 원리를 일반화하면, 어떤 수 i가 소수가 아니라면, i의 두 약수 중 하나는 반드시 √i 이하.
그러니까 √i까지만 나눠보면 충분하게 된다..

---

4. √i까지만 확인하는 게 왜 빠를까?

시간 복잡도 비교

1. 모든 숫자를 다 나누는 경우
   • O(N): 최대 N-1번 검사해야 함.
   • 예: 100이면 99번 검사.
2. √N까지만 나누는 경우
   • O(√N): i가 클수록 엄청나게 줄어듦.
   • 예: 100이면 10번만 검사하면 됨.

차이점 예시

N (입력 숫자)	검사 횟수 (O(N))	검사 횟수 (O(√N))
100	99	10
10,000	9,999	100
1,000,000	999,999	1,000

 

N이 커질수록 성능 차이가 커지는 걸 볼 수 있다.

---

5. 정리

• √i까지만 확인해도 소수 판별이 가능하다.
• 소수가 아닌 수는 반드시 √i 이하의 약수를 가진다.
• O(N)에서 O(√N)으로 줄여서 훨씬 빠르게 소수를 판별할 수 있다.