[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)

소수

소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수라고 부른다.

 

예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

 

소수 구하기

주어진 수가 소수인지 판별하는 문제는 소수에 관련된 가장 기초적인 문제이다. 주어진 수 n이 소수인지를 판단하는 가장 단순한 방법은 2부터 n-1까지의 모든 수를 순회하면서 이 중 n의 약수가 있는지 확인하는 것이다. 약수가 하나도 없다면 n이 소수란 사실을 알 수 있다. 거기에 합성수 n이  p*q로 표현될 때 한 수는 항상 \(n^{1\over2}\)이하, 다른 한 수는 \(n^{1\over2}\) 이상이라는 점을 이용하면 n-1까지 순회하지 않고  \(n^{1\over2}\)까지만 순회하도록 최적화할 수 있다.

// O(n^(1/2)) 루트n 시간에 동작하는 소수 판별 알고리즘
static boolean checkIsPrimeNumber(int num) {
	for(int i=2 ; i*i<=num; i++) {
		if(num%i ==0) {
			return false; //num이 i의 배수면 소수가 아니므로 false
		}
	}
	return true;
}

 

이를 최적화할 방법은 여러가지가 있다. 2와 3을 제외한 소수는 6k+1, 6k-1의 형태를 띤다는 사실을 이용할 수도 있고, 작은 소수들의 목록을 미리 만들어 놨다가 이들로 먼저 나누는 방법을 시도해 봐도 된다. 하지만 이와 같은 최적화는 자주 쓰이지 않는다. 판단해야 할 수가 많지 않을 때는 이런 단순한 코드로 충분하고, 판단해야 할 수가 많을 때는 해당 방식으로 아무리 최적해봐야 소용 없기 때문이다.

 

많은 수에 대해 소수 판단을 해야 할 때는 대개 다음에서 소개할 에라토스테네스의 체를 이용해 특정 범위의 숫자들에 대해 미리 소수 판단을 해두는 방법을 사용하게 된다.

 

소수 구하기 - 에라토스테네스의 체

프로그래밍 대회에서 소수 관련 문제를 풀 때 가장 자주 사용되는 방버은 바로 에라토스테네스의 체이다.  다음은 에라토스테네스의 체는 소수를 찾는 간단한 알고리즘이다. (위키피디아 참고)

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

 

에라토스테네스의 체 구현

2부터 시작하여 자신의 배수가 되는 수를 지워나가면 된다. 만약 120까지의 소수를 구한다고하면 \(11^2 > 120\)이므로 11보다 작은 수의 배수들만 지워도 충분하다. 

• 지워지지 않은 수를 찾을 때 n이 아니라 \(n^{1\over2}\)까지만 찾는다. 이것은 위의 소수 판정 알고리즘과 똑같은 최적화 방식이다.
• 또한, i의 배수들을 모두 지울 때 i*2에서 시작하는 것이 아니라 i*i에서 시작하는 것이다.  2*i는 이미 2의 배수를 지울 때 지워졌고 3*i는 이미 3의 배수를 지울 때 지워졌기 때문이다.
  • i*k (k < i)까지는 이미 검사되었으므로 j시작 값은 i*2에서 i*i로 개선할 수 있다. (k의 최댓값은 i-1이므로)
• 만약 isPrime[i]가 true이면, i 이후의 i 배수는 약수로 i를 가지고 있는 것이 되므로 모두 true값을 준다.
• 만약 isPrime[i]가 false이면, i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니게 된다. 그러므로 검사할 필요가 없다.

public class Prime {

	public static void main(String[] args) {
		int n = 120;
		boolean[] isPrime = new boolean[n+1];
		Arrays.fill(isPrime , true);
        
		// 소수는 true
		// 0, 1은 소수가 아니므로 false
		isPrime [0] = isPrime [1] = false;
		for(int i=2; i*i<=n; i++){
			// 만약 i가 소수 혹은 아직 지워지지 않았다면
			if(isPrime[i]){
				// i의 배수 j들에 대해 isPrime[j] = false; 로 둔다.
				// i*i미만의 배수는 이미 지워졌으므로 신경쓰지 않는다.
				for(int j=i*i; j<=n; j+=i) {
					isPrime[j] = false;                
				}
			}        
		}    
		// 1 ~ 120 사이의 소수 출력
		for(int i=1; i<=n ;i++){
			if(isPrime[i]) System.out.print(i+" ");        
		}
	}
}

 

실행결과

 

 

소인수 분해

한 합성수를 소수들의 곱으로 표현하는 방법을 찾는 소인수 분해(prime factorization) 또한 프로그래밍 대회에서 종종 볼 수 있는 주제이다. 소인수 분해를 하는 가장 쉬운 방법은 위에서 다룬 간단한 소수 판별 알고리즘을 응용하는 것이다. 2부터 시작해 n이 소인수가 될 수 있는 수들을 하나하나 순회하면서, n의 약수를 찾을 때마다 n을 이 숫자로 나눈다. 

 

이 알고리즘은 n이 소수인 경우 \(n^{1\over2}\)번 반복문을 돌기 때문에 시간복잡도는  \(O(n^{1\over2})\)이 된다.  

public class PrimeFactorization {
	public static void main(String[] args) {
		List<Integer> list = new ArrayList<>();
		int n = 120;
		for(int i=2; i*i<=n; i++) {
			while(n%i==0) {
				list.add(n);
				n/=i;
			}
		}
		
		if(n>1) list.add(n);
		for(int num : list) {
			System.out.print(num+" ");
		}
		System.out.println();
	}
}

 

실행 결과