[정수론] 에라토스테네스의 체와 소인수 분해

에라토스테네스의 체

 

 

"에라토스테네스의 체(Sieve of Eratosthenes)"는 3세기의 그리스 수학자 에라토스테네스가 정리한 소수를 찾는 방법이다.

 

n이하의 자연수에서 소수의 배수를 차례대로 소거하여 최종적으로 n이 남아있다면 n은 소수임을 알아낼 수 있다.

 

출처: 위키백과 

에라토스테네스의 체 구현에는 해당 수가 소수인지 아닌지만 저장하는 bool형의 자료구조가 필요하며, 아래 두 가지의 최적화를 거친다.

 

1. n이 인수가 있다면 인수는 √n 이하의 수와 그 이상의 수의 쌍으로 이루어지기 때문에 √n의 수까지만 확인해도 판정이 가능하다.

 

2. i의 배수를 지울때는 i*i이하의 값들은 이미 i이하의 값의 배수(ex. i*3, i*4, i*5 ... i*(i-1) 는 이미 소거)이므로 i*i이상의 값부터 소거하면 된다.

 

 

	const int MAX_NUM = 1000;
	bool is_prime[MAX_NUM+1];
	void SieveEratos(){
	memset(is_prime, true, sizeof(is_prime));
	int sqrtn = int(sqrt(MAX_NUM));
	is_prime[0]= is_prime[1] = false;
	for(int i=2; i<=sqrtn ; ++i)
	if(is_prime[i])
	for(int j= i*i; j<=MAX_NUM ; j+=i)
	is_prime[j] = false;
	}

view raw [알고리즘]에라토스테네스의 체.cpp hosted with ❤ by GitHub

 

 

소인수 분해 알고리즘

 

 

이제 에라토스테네스의 체를 이용하여 구현하는 빠른 소인수 분해 알고리즘을 알아보자.

 

해당 알고리즘은 n의 가장 작은 소인수만을 min_factor[n]에 저장하여 소인수 분해를 구현한다.

모든 수에대하여 min_factor를 구했다면 n이 1이 될 때까지 min_factor[n]로 나누어준 값들의 min_factor들이 n의 소인수를 구성한다.

 

ex. 28(min_factor =2) -> 14(min_factor =2) -> 7(min_factor =7) -> 1(종료)

2 x 2 x 7 = 28

 

 

	const int MAX_NUM = 1000;
	int min_factor[MAX_NUM+1];
	void SieveEratos(){
	int sqrtn = int(sqrt(MAX_NUM));
	for(int i=2; i<=MAX_NUM ; ++i)
	min_factor[i] = i; //일단 모든 min_factor를 i 값을 해당 값으로 초기화
	for(int i=2; i<=sqrtn ; ++i)
	if(min_factor[i] == i) //i가 소수인 경우만
	for(int j = i*i; j<=MAX_NUM ; j+=i)
	if(min_factor[j] ==j ) //체로 걸러지지 않은 경우 i가 j의 최소 소인수이다.
	min_factor[j] = i;
	}
	//n의 소인수들을 반환
	vector<int> factor(int n){
	vector<int> ret;
	while(n>1){ //n이 1이 될때 까지
	ret.push_back(min_factor[n]);
	n /= min_factor[n];
	}
	return ret;
	}

view raw 에라토스테네스 소인수 분해.cpp hosted with ❤ by GitHub