소수를 구하는 알고리즘

소수

2를 제외한 자연수 중 나누어 떨어지는 수가 1과 자신뿐인 수

소수를 구하는 알고리즘

가장 기본적인 방법

정의를 그대로 구현한 것으로 2 부터 주어진 수 - 1 까지의 자연수로 계속 나누어 본다.

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

• O(n)의 시간복잡도를 가진다.
• 하지만, 숫자가 주어질 때 마다 판별해야한다.
  

메모이제이션

2 부터 n 사이의 소수로 나누었을 때 떨어지지 않으면 수수다.

ArrayList<Integer> getPrimes(int n){
  ArrayList<Integer> memo = new ArrayList<>();
  memo.add(2);

  for(int i = 2 ; i <= n ; ++i){
    for(int j = 0 ; j < memo.size() ; ++j){
      if(i % memo.get(j) == 0) break; // 소수로 나누어 떨어지면 소수가 아니다.
      if((j + 1) == memo.size()) memo.add(i); // 이전까지의 모든 소수로 나누어 떨어지지 않으면 소수다.
    }
  }
}

• n 까지의 모든 소수를 판별해낸다.
• O(n^2)의 시간복잡도를 가진다.

에라토스테네스의 체

2 부터 시작하여 소수의 배수를 모두 걸러낸다.

boolean[] getPrimes(int n){
  boolean[] composite = new boolean[n + 1];
  composite[1] = true;
  
  for(int i = 2 ; i <= n ; ++i){
    if(composite[i]) continue; // 소수가 아닌(true) 수는 넘어가기
    for(int j = i + i ; j <= n ; j += i){ // i를 제외한 i의 배수 모두 체크하기
    	composite[j] = true;
    }
  }
}

• n 까지의 모든 소수를 판별해낸다.
• O(nloglogn)의 시간복잡도를 가진다.

제곱근 이용하기

소수는 2 ~ (N-1)범위에서 약수를 가지지 않는다. 또한 약수가 존재하는 숫자의 약수들 중 반은 1 ~ sqrt(N)범위에 존재한다. 즉, 소수임을 판단하기 위하여 약수를 검사할 때 2 ~ sqrt(N)까지만 검사하면, 전체 범위에서 약수의 존재 여부를 확신할 수 있다.

...
for(int i = 2 ; i <= sqrt(n) ; ++i){
...

문제

• BOJ 1978 소수 찾기
• BOJ 1929 소수 구하기
• BOJ 6588 골드바흐의 추측
• BOJ 17103 골드바흐 파티션