소수를 구하는 효율적인 방법

개요

입력받는 숫자가 소수인지 판별하는 알고리즘 문제를 풀었다.

코드 구현

public static boolean isPrime(int number) {
	boolean isPrime = true;
	for(int i = 2; i < number; i++) {
		if(number % i == 0) {
			isPrime = false;
			break;
		}
	}
	return isPrime;
}

시간복잡도는 $O(N)$ 이다.

몇 가지 의문이 생겼다. 2 ~ (number - 1) 까지 다 돌아야 될까? 더 효율적인 방법이 있을까? 라는 고민을 하게 되었다.

제곱근 나누기

$number = i \times j$ 라고 한다면, 반드시 $i <= \sqrt number$ $j >= \sqrt number$ 를 만족한다.

예시 1

$12 = i \times j\\ 1 \times 12\\ 2 \times 6\\ 3 \times 4\\ 4 \times 3\\ 6 \times 2\\ 12 \times 1$

$i$ 는 3까지만 순환하면 4, 6, 12까지 순환하지 않아도 된다.

예시 2

$16 = i \times j\\ 1 \times 16\\ 2 \times 8\\ 4 \times 4\\ 8 \times 2\\ 16 \times 1\\$

$i$ 는 4까지만 순환하면 8, 16까지 순환하지 않아도 된다.

결론적으로 $i \leq \sqrt num \rarr$ $i^2 \leq num \rarr$ $i \times i \leq num$ 이다.

코드 구현

public static boolean isPrime(int number) {
	boolean isPrime = true;
	for(int i = 2; i * i <= number; i++) {
		if(number % i == 0) {
			isPrime = false;
			break;
		}
	}
	return isPrime;
}

시간복잡도는 $O(\log{N})$ 이다.

하지만 대량의 숫자들에 대해 소수 여부를 판별해야 할 때에는 제곱근 나누기 방법보다는 다음에 소개할 에라토스테네스의 체 방법을 사용한다. 제곱근 나누기 방법은 모든 숫자를 판별해야 되지만 에라토스테네스의 체는 앞에서 구한 소수의 배수를 이용하여 미리 판별할 수 있다.

에라토스테네스의 체

다음은 에라토스테네스의 체 알고리즘이다.

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

코드 구현

public static void eratos(int number) {
	boolean[] isPrimes = new boolean[number + 1];
	Arrays.fill(isPrimes, true);
	for (int i = 2; i * i <= number; i++) {
    	if(!isPrimes[i]) {
        	continue;
        }
      	for (int j = i * i; j <= number; j+=i) {
        	isPrimes[j] = false;
            
  		}
  	}
    for (int i = 2; i <= number; i++) {
        if (isPrimes[i]) {
              System.out.println(i);
        }
    }
}

시간복잡도는 $O(N\log{(\log{N})})$ 이다.

참고자료

• https://loosie.tistory.com/26
• https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%86%8C%EC%88%98%EC%9D%98-%ED%8C%90%EB%B3%84-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4
• https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4