[Algorithm] 소수 판별법 - 에라토스테네스의 체

ㅎㅎ·2023년 1월 12일

algorithm

Algorithm

목록 보기

1/2

📖 소수 구하기

어떤 자연수 N이 소수인지 판별하는 방법에는 여러가지 방법이 있다.

1. N을 2부터 N-1까지 모두 나누기

소수는 1 또는 자기 자신으로만 나누어지기 때문에 위의 방법으로 나누어 떨어지지 않는다면 그 수는 소수라고 할 수 있다.

만약, $N$ 이 어떤 두 수로 나누어진다고 한다면, $N = p*q$ 의 형태가 되고, p와 q 둘 중 하나는 반드시 $\sqrt{N}$ 의 값 이하일 것이다.

따라서 $\sqrt{N}$ 까지만 나눠도 소수인지 판별 가능하다.

이 방법의 단점:
시간 복잡도가 $O(\sqrt{N})$ 이기 때문에 N이 커지면 소수를 판별하는데 시간이 오래 걸린다.

N이하의 소수를 모두 구하라고 한다면 $O(N\sqrt{N}$ )의 시간 복잡도를 갖기 때문에 $N$ 의 범위가 매우 제한적이다.

2. '에라토스테네스의 체' 사용하기

어떠한 자연수 N이 소수인지를 판별하는 방법 중 고대 그리스 수학자 에라토스테네스가 발견한 에라토스테네스의 체가 가장 보편적으로 이용된다.

에라토스테네스의 체는 초기값이 0인 N개의 원소를 갖는 배열(A)를 선언하여, i=2부터 i=N까지 순서대로 돌면서 소수가 아닌 수를 체크해주는 방식으로 소수를 판별한다.

결국 i가 소수인 경우에만 A[i] = 0이 되고, 나머지는 모두 1이 된다.

소수의 배수들은 모두 합성수라는 성질을 이용하여 체로 걸러내듯이 합성수들을 모두 걸러내는 방법이다.

시간 복잡도는 $O(n\log(\log n))$ 으로, 보통 100만까지 정도의 소수를 구하는 문제가 출제된다.

#include <stdio.h>

int main() {
	int arr[1001] = {0};
    for(int i=2; i<=1000; i++) { // 합성수 걸러내는 반복문
    	if(arr[i] == 0) {
        	for(int j=2; i*j<=1000; j++) {
				arr[i*j] = 1; // 합성수 체크  
            }
        }
	}
    
    for(int i=2; i<=1000; i++) { // 걸러낸 소수 출력
    	if(arr[i] == 0) {
        	printf("%d ", i);
        }
    }
    return 0;
}

🖥 출력 결과: 에라토스테네스의 체 결과

📌 '에라토스테네스의 체' 의 활용

1) 각 2 부터 n 까지의 자연수 k 에 대해 "k가 갖는 가장 작은 소인수" 를 계산하는 방법

에라토스테네스의 체 원리를 생각해보면, 현재 수가 아직 걸러지지 않았다면 그 수는 소수이고, 현재 수의 배수드를 제거해나가는 방식이다.

이때 제거되는 수는 합성수이고, 제일 처음 제거될 때 이용되는 소수가 k가 갖는 가장 작은 소인수이다.

int prime[1000001];
int main() {
	int n = 1000000;
    for(int i=1; i<=n; i++) { prime[i] = i; }
    
    for(int i=2; i<=n; i++) {
    	if(prime[i] == i) { // 아직 걸러지지 않음
        	for(int j=2; i*j<=N; j++) { // i의 배수
            	if(prime[i*j] == i*j) { prime[i*j] = i; }
            }
        }
}

2) 각 2 부터 n 까지의 자연수 k 에 대해, "빠르게 k를 소인수분해" 하는 방법

자연수 k를 소인수분해를 하는 가장 기초적인 방법은 직접 2부터 $\sqrt{k}$ 까지 나눠주는 방법이다.
만약, 현재 k가 i로 나누어떨어지면 i로 더이상 나누어떨어지지 않을 때까지 나눠준다. 나누어지는 횟수 만큼 소인수 i가 k에 포함되어있는 것이다.''
$\sqrt{k}$ 까지 모두 나누어주었을 때, 아직 k가 1이 아니라면, 이 또한 $\sqrt{k}$ 보다 큰 소수 이며, 기존의 k의 소인수가 된다.

하지만 이 방식으로 2부터 n까지의 모든 자연수 k에 대해 소인수분해를 한다면 $O(n\sqrt{n})$ 의 시간 복잡도를 가지게 된다.

1번에서 설명한 k가 갖는 가장 작은 소인수를 이용하면 $O(n\log n)$ 만에 2 부터 n까지의 모든 자연수를 소인수분해할 수 있다.

각 2부터 n까지 모든 자연수의 가장 작은 소인수를 전처리 해두었다고 가정하자.
그러면 자연수 k에서 시작해서, 가장 작은 소인수를 나누어주는 과정을 반복하면 소인수분해가 완성된다.
여기서 가장 작은 소인수는 항상 2 이상이므로 $O(log k)$ 안에 가능하다.

int prime[1000001];
vector<int> fac[1000001]; // cpp의 문법이다.
int main(void) {
	int N = 1000000;
    for(int i=1; i<=N; i++) { prime[i] = i; }
    
    for(int i=2; i<=N; i++) { // 1번과 같은 코드
    	if(prime[i] == i) {
        	for(itn j=2; j*i<=N; j++) {
            	if(prime[i*j] == i*j) { prime[i*j] = i; }
            }
        }
    }
    
    for(int i=2; i<=N; i++) {
    	int k = i;
        while (k > 1) {
        	fac[i].push_back(prime[k]); // 소인수 삽입
            k /= prime[k];
        }
    }
    
    /* 출력 코드
    for (int i=2; i<=N; i++) {
		cout << i << " = ";
		for (int j = 0; j < fac[i].size(); j++) {
			cout << fac[i].at(j) << " ";
		}
		cout << endl;
	}
    */

	return 0;
}