1보다 큰 자연수 N을 입력받았을 때, N 이하의 소수(Prime Number)를 모두 구하시오.
방법1: 하나씩 다 나눠보기
어떤 수가 소수인지 아닌지 판별하는 방법
소수(Prime Number)란 1과 자기 자신만 약수로 가지는 수로, 다시 말해 1과 자기 자신으로만 나누어 떨어지는 수이다.
(단, 1은 소수가 아니다.)
그렇다면 특정 자연수 N이 소수인지 판별하려면 어떻게 해야 할까?
답은 어렵지 않다. 2부터 N-1까지의 숫자들로 나눠본 후, 나머지가 0인 경우가 하나라도 있으면 소수가 아닌 수이다.
is_prime = True
for i in range(2, N):
if N % i == 0:
is_prime = False
break
print("소수" if is_prime else "소수가 아님")
N 이하의 소수 모두 찾기
이제 소수인지 아닌지를 구하는 방법을 알았으니, N 이하의 소수도 쉽게 찾을 수 있겠다.
그냥 1부터 N까지 숫자들을 모두 소수인지 아닌지 확인하면 되겠다.
# 소수 판별 함수
def is_prime(number):
for i in range(2, number):
if number % i == 0:
return False
return True
for i in range(2, N + 1):
if is_prime(i):
print(i)
시간 복잡도
먼저 소수 판별 함수를 보자. 어떤 수 N이 들어오면 2부터 N-1까지의 수로 모두 나눠봐야 함으로 $O(N)$의 시간이 걸린다.
따라서 이 함수를 2부터 N까지의 모든 수에 사용하는 위 코드는 $O(N^{2})$의 시간 복잡도를 가진다.
조금 더 시간을 줄여볼까?
현재는 소수 판별 함수에서 2부터 N-1까지의 수로 N을 나눠보고 있지만, 이 수의 범위를 좀 더 줄일 수 있다.
$N = a * b$ $(a \leq b)$로 식을 세워보자. 이때 a가 될 수 있는 가장 큰 수는 $\sqrt N$이다.
우리는 a에 해당되는 숫자로만 나눠보면 된다. (a가 약수이면 대응되는 b도 약수이기 때문이다.)
이렇게 수정하면 시간 복잡도를 $O(N\sqrt N)$으로 줄일 수 있다.
import math
# 소수 판별 함수
def is_prime(number):
sqrt = int(math.sqrt(number)) + 1
for i in range(2, sqrt):
if number % i == 0:
return False
return True
방법2: 에라토스테네스의 체
이렇게 숫자 하나 하나씩 소수인지 확인하는 것은 범위가 커질수록 계산량이 급증한다.
이를 대체할 수 있는 방법 중 하나가 바로 에라토스테네스의 체이다.
소수가 아닌 수 걸러내기
에라토스테네스의 체는 N 이하의 모든 자연수들을 소수라고 둔 다음, 소수가 아닌 수들을 순차적으로 지워나가는 방식이다.
1. 먼저 배열에 2부터 N까지의 자연수들을 넣어 놓는다.
2. 배열의 맨 앞에는 2가 있다. 배열에서 2를 제외한 2의 배수를 모두 지운다.
3. 2 다음에는 3이 있다. 배열에서 3을 제외한 3의 배수를 모두 지운다.
4. 3 다음에는 5가 있다. (4는 2의 배수이므로 지워졌다.) 5를 제외한 5의 배수를 모두 지운다.
5. $\sqrt N$ 이상인 수를 만날 때까지 반복한다. (1.3 참고)
N이 20일 때를 그림으로 나타내면 아래와 같다.
($\sqrt{20} < 5$이므로 3까지만 수행한다.)
코드로 구현해보기 (Python)
import math
is_prime = [True] * (N + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(math.sqrt(N)) + 1):
if is_prime[i]:
for j in range(i * 2, N + 1, i):
is_prime[j] = False
print(*filter(lambda x : is_prime[x], range(N + 1)))is_prime이라는 리스트를 이용해 특정 숫자가 소수인지 아닌지를 기록하였다.
0과 1은 소수가 아니므로 False로 지정했고, 이후 2부터 $\sqrt N$까지 반복문을 돌며 i의 배수들을 False로 지정해두었다.
마지막으로 is_prime이 True인 숫자들만 출력해주면 된다.
만약 소수를 순서 상관 없이 구해도 된다면, set을 이용해서 더욱 간결한 코드를 짤 수 있다.
(다만 set의 차집합 연산에는 O(두 집합의 크기의 합)이 소요되므로, 조금 덜 효율적이다.)
import math
primes = set(range(2, N + 1))
for i in range(2, int(math.sqrt(N)) + 1):
if i in primes:
primes -= set(range(i * 2, N + 1, i))
print(*primes)
시간 복잡도
에라토스테네스의 체의 시간복잡도는 $O(N\log_2(\log_2 N))$이다. (증명 과정이 복잡하다.)
따라서 특정 범위 안의 소수를 모두 구할 때는 효율적이며, 특정 숫자 하나의 소수 판정에는 비효율적이다.
관련 문제 (BOJ)
- [2960] 에라토스테네스의 체: 에라토스테네스의 체 구현 방법을 연습할 수 있는 문제
- [1929] 소수 구하기: 에라토스테네스의 체를 그대로 쓰면 되는 문제
- [9020] 골드바흐의 추측: 구한 소수를 사용해서 정답을 맞추는 문제
- [1016] 제곱 ㄴㄴ 수: 에라토스테네스의 체를 변형해서 써야 하는 문제
- [1017] 소수 쌍: 소수 구하기 + 이분 매칭 문제
코드는 여기에서 확인할 수 있다.
