[알고리즘] 소수(Prime Number) 구하기 - Java

목차

1. 소수
2. 소수 구하기
3. 에라토스테네스의 체(Sieve of Eratosthenes)

소수

소수 (prime number) 는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수 입니다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의됩니다.

 

예를 들어, 7은  \(1 \times 7 \), \(7 \times 1\) 로 7, 1 만 약수로 가지기 때문에 소수입니다.

그러나 6은 \( 2 \times 3 \) 이라는 자신보다 작은 두 숫자의 곱 으로 나타낼 수 있기 때문에 소수가 아닙니다.

이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수 라고 합니다.

소수 구하기

주어진 수가 소수인지 판별하는 문제는 가장 기초적인 문제입니다.

가장 간단한 방법으로는 2부터 n-1 까지의 모든 수를 순회하면서 이 중에 n의 약수가 있는지 확인 하는 것입니다. 약수가 하나도 없다면 n 이 소수라는 것을 알 수 있습니다. 

public static boolean IsPrimeNumber(int number)
{
	// 2 부터 number 까지 전체 순회
	for(int i=2; i<number; ++i)
	{
    	// 나누어서 떨어진다면 약수
		if (number% i == 0)
			return false;
	}
	return true;
}​

하지만 해당 방식은 \(O(n)\) 의 시간복잡도를 가집니다. 

그래서 합성수 의 특징을 이용하여 순회 횟수를 최적화 할 수 있습니다. 

합성수는 \( n \) 은 \( n = p \times q \) 로 표현 가능합니다.

여기서 \( p \) 가 \( \sqrt{n}\)  이상이라면 , \( q \)  는 \( \sqrt{n}\)  이하가 됩니다. 

 

예를 들어, 64 이라는 합성수가 있습니다. 64의 약수들은

1, 2, 4, 8, 16, 32 ,64 이 있습니다. 

이 수들은 \( 1 \times 64\), \( 2 \times 32 \) ,\( 4 \times 16 \) ,\( 8 \times 8 \) 로 나타낼수 있고

위에서 설명한 대로 \( \sqrt{n}\)  이상과 , \( \sqrt{n}\)  이하의 수로 만들어 진 것을 확인 하실수 있습니다. 

 

위 합성수의 특징 을 통해 우리는 \( O(\sqrt{n}) \) 까지만 확인 하여도 된다는 것을 알 수 있습니다. 

소스코드로 확인해보겠습니다. 

public static boolean IsPrimeNumber(int number)
{
	/*
	sqrt 연산을 사용하지 않고 제곱 형태로 사용하여도 된다.
	double sqrtNumber = Math.sqrt(number);
	for(int i=2; i<=sqrtNumber; ++i)
	*/
	for(int i=2; i*i<=number; ++i)
	{
		if (number % i == 0)
			return false;
	}
	return true;
}

이렇게 소수를 구하는 방법에 대해서 알아보았습니다.

하지만 특정 수 가 아닌 많은 수에 대해 소수 판단을 해야 할 경우에는 에라토스테네스의 체 를 이용합니다. 에라토스테네스의 체에 대해서 알아보도록 하겠습니다.

소수 구하기 - 에라토스테네스의 체(Sieve of Eratosthenes)

코딩테스트나 프로그래밍 대회에서 소수 관련 문제를 풀 때 자주 사용하는 방법입니다. 

간단한 알고리즘을 소개하겠습니다.

 

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

에라토스테네스의 체

알고리즘을 토대로 구현을 해보겠습니다.

number 까지 소수인경우 \( true \), 소수가 아닌 경우 \( false \) 를 return 하는 함수이다. 

public static boolean[] Eratosthenes(int number)
{
	boolean[] isPrime = new boolean[number+1];
    // 소수는 true
	Arrays.fill(isPrime , true);
     
	// 0, 1은 소수가 아니므로 false
	isPrime [0] = isPrime [1] = false;
		
	for(int i=2; i*i<=number; i++){
		if(isPrime[i]){
			// i 의 배수들도 소수가 아니므로 false 로 만든다.
			for(int j=i*i; j<=number; j+=i) {
				isPrime[j] = false;                
			}
		}        
	}   
	return isPrime;
}