알고리즘 - 에라토스테네츠의 체 : 소수와 수인수분해

 

 

백준 문제를 푸는 도중에 에라토스테네스의 체 라는 효율적인 알고리즘을 공유해보고자 이글을 적습니다.

 

소수는 약수가 자기 자신과 1만 있는 숫자를 말하는데, 단순 반복문으로도 구할수 있습니다. 

 

작은 수에 대한 소수를 구할때는 반복문으로 구해도 괜찮지만 숫자들이 커지면 반복문으로 

판별하는것은 시간낭비입니다. 

 

이때 알고리즘 '에라토스테네스의 체 '를 사용합니다. 

에라토스테네스의 체 : 

 - 체처럼 걸러낸다고 하여 붙여진 알고리즘은 2이상 n이하의 정수 x가 소수인지 아닌지를 효율적으로 판단할 수 있도록 추가적인 배열을 만드는 전처리 알고리즘 입니다.  

배열 array[x] =0 이면 소수이고 1이면 소수가 아니다라고 정의할수 있습니다. 

 

초기의 모든 값은 0으로 되어있습니다. 

2부터 차례대로 정수를 살펴 볼때 2는 소수이기 때문에 2의 배수들은 전부 1로 표시합니다. 

예를들면 array[4]=array[6]=array[8] ..... 등이 1로 표현됩니다. 

검사를 다 하지 않아도 쉽게 1로 표시할수 있습니다. 

 

3은 array[x]=0 이며 따라서 소수입니다 3의 배수들은 전부 1로 표시합니다. 

4는 이미 1로 판별이 되어서 건너뜁니다. 

5는 array[5]=0 이므로 소수이고 5의 배수들은 전부 1로 표시합니다. 

 

쭉 이런식으로 새로운 소수 x를 발견할때마다 그 소수의 배수들은 모두 소수가 아니라고 표시를 하는겁니다. 

 

이렇게 하면 반복문 내에서 건너뛸 수 있는 숫자들이 많아지므로 숫자 하나하나마다 일일이 나누기 등을 해가면서 소수인지 하나씩 판단하는것보다 매우 빨라지게 됩니다. 

 

알고리즘 수행 시간이 O(nlog*log_n)임을 보일수 있는데 이것은 O(n)에 매우 근접한 시간 복잡도라고 합니다. 

 

위의 코드에서 안에 있는 반복문은 x가 소수일때만 수행되기 때문에 사실 알고리즘의 수행 상한보다 더 효율적입니다. 

 

예시 코드를 보시면 더욱 쉽게 아실수 있습니다. 

//소인수 분해 

for(int i =0; n>1; i++){
	if(array[i]==0){
		while (n %i ==0){
			printf("d%",i);
			n/=i; }
			}
		}
   }

i가 소수였을경우

그리고 n이 소수로 나누어 떨어진다면 그 소수를 출력하고 n을 소수로 나눈훈 다시 반복하는 작업의 코드입니다. 

 

백준 문제들중에 소수 관련 문제를 푸시게 되면 더욱더 이해하실수 있을겁니다.