[알고리즘] 소수 구하기 (아리토스테네스의 체)

소수(Prime Number) 를 판별하는 방법을 알아보자.

 

소수란?

1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다.

ex.

3 : 1과 3을 약수로 가짐

5 : 1과 5를 약수로 가짐

 

소수 구하기

자연수 N이 소수인지 판별하는 방법에는 다음과 같은 방법들이 있다.

2부터 N-1으로 나눠 보기

말 그대로 자연수 N을 2부터 N-1까지 나눠 떨어지는지 확인하는 방법이다.

ex.

N = 7
7 % 2 = 1
7 % 3 = 1
7 % 4 = 3
7 % 5 = 2
7 % 6 = 1

7은 2부터 6까지의 수로 나눠 떨어지지 않으므로 7은 소수이다.

이 방법의 시간복잡도는 O(N)으로 더 최적화 할 방법이 있다.

 

2부터 √N으로 나눠 보기

이 방법은 N을 2부터 √N까지 나눠 떨어지는지 확인하는 방법이다. √N까지만 나눠도 되는 이유는 다음과 같다.

1. 어떤 수 X를 합성수(소수가 아닌 수)라고 하자.
2. X = M*N (M ≥ N) 이라고 할 수 있다.
3. M ≥ N 이므로 N*N ≤ M*N 
4. N*N ≤ X
5. N ≤ √X
6. X = M*N (N ≤ √X, M ≥ √X)

∴ √X이하의 수로만 나눠도 X가 합성수인지 소수인지 판별할 수 있다.

 

위와 같은 성질을 다음과 같이 이용할 수 있다.

N = 7
√N = 2.XXXX
int(√N) = 2

7 % 2 = 1

7은 2로 나눠떨어지지 않으므로 7은 소수이다.

이 방법의 시간복잡도는 O(√N)이다. 하지만 아리토스테네스의 체를 이용하면 시간복잡도를 줄일 수 있다.

 

아리토스테네스의 체

아리토스테네스의 체의 방법은 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 
2. 2는 소수이므로 남겨두고 자기 자신을 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 3은 소수이므로 남겨두고 자기 자신을 제외한 3의 배수를 모두 지운다.
4. 남아있는 수 가운데 5는 소수이므로 남겨두고 자기 자신을 제외한 5의 배수를 모두 지운다.
5. 남아있는 수 가운데 7은 소수이므로 남겨두고 자기 자신을 제외한 7의 배수를 모두 지운다.
...
주어진 수가 N이라면, 위의 과정을 √N 미만의 소수까지만 반복한다.

N = 16
1. 숫자 나열 : 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16
2. 2의 배수 제거 : 2, 3, 5, 7, 9, 11, 13, 15
3. 3의 배수 제거 : 2, 3, 5, 7, 11, 13, 15

아리토스테네스의 체의 시간복잡도는 O(n log(log n))이다. 

 

적용

이제 아리토스테네스의 체를 이용하여 백준 4948번: 베르트랑 공준 문제를 풀어보자.

문제

0이 입력될때 까지 자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 문제이다.

풀이

여러번 소수를 구해야 하고, n의 범위도 1 ≤ n ≤ 123,456이므로 123,456까지 나열하고 아리토스테네스의 체를 이용하면 시간 복잡도를 줄일 수 있다.

import sys

isPrime = [True for i in range(123456*2)]		#소수를 True라고 저장하는 배열

for i in range(2, int(len(isPrime)**0.5)):
    if isPrime[i]:
        for ii in range(i+i, len(isPrime), i):	#해당 숫자가 소수면 그 배수부터 False라고 저장
            isPrime[ii] = False

while True:
    n = int(sys.stdin.readline())

    if n == 0: break
    if n == 1: 
        print(1)
        continue

    ans = 0
    for i in range(n+1, 2*n):
        if isPrime[i]: ans += 1

    print(ans)

 

 

 

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

4948번: 베르트랑 공준