알고리즘 - 소수 구하기

소수 (Prime Number)

---

소수란 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 의미합니다.

 

알고리즘에서 소수를 구하는 문제가 간혹 나오곤 하기 때문에 어떤 식으로 소수를 구하는지 알아두면 좋습니다.

 

브루트 포스로 구하기

---

가장 간단한 방법으로 2부터 n-1까지 돌면서 약수가 있는지 확인하는 방법입니다.

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

 

하지만 위의 경우 O(N)의 시간복잡도를 가지므로, 큰 수 여러 개가 소수인지 파악할 땐, 효율적이지 못합니다.

 

위의 방식을 조금 더 효율적으로 구현한 방법이 바로 아래 방법입니다.

// i * i 방식
public static boolean isPrime1(int n) {
   if(n < 2) return false;
   
   for (int i = 2; i * i <= n; i++) {
      if (n % i == 0) return false;
   }
   return true;
}

// sqrt를 이용한 방식
public static boolean isPrime2(int n) {
   if(n < 2) return false;

   for (int i = 2; i  <= Math.sqrt(n); i++) {
      if (n % i == 0) return false;
   }
   return true;
}

주어진 수를 합성수라고 생각했을 때, n =  a * b 로 정의할 수 있습니다. 이때, a < b 라면 a < √n , √n < b 가 반드시 성립합니다.

 

따라서,  a와 b 중 더 작은 쪽의 숫자와 비교해 약수가 없다면 소수가 됩니다. 즉, n까지 반복문을 돌릴 필요 없이 √n 까지만 반복문을 돌려보면 답이 나옵니다. 

 

시간복잡도는 O(√n)이 나옵니다.

 

 

에라토스테네스의 체로 구하기

---

에라토스테네스의 체

2를 제외한 2의 배수를 전부 지우고, 3을 제외한 3의 배수를 전부 지운 후, 그중 작은 값부터 지워지지 않은 값을 소수로 인식하여 그 소수로 계속해서 배수를 제거하는 방식입니다.

 

한 번에 소수를 여러 개 구할 수 있다 보니, 보통 여러 수가 주어지며 각 수들이 소수인지 판별할 때 사용됩니다.

 

public static void findPrime(int n) {

   // 소수 체크용 배열
   boolean[] prime = new boolean[n + 1];

   // 일단은 전부 소수라고 가정 (이 과정을 생략하고 역으로 false를 이용해도 됩니다)
   Arrays.fill(prime, true);

   // 0, 1은 소수가 아니므로 false
   prime[0] = prime[1] = false;

   // 루트 n 까지만 반복하면 소수를 구할 수 있으므로 루트 n까지만 반복
   for (int i = 2; i * i <= n; i++) {
      // 소수면 소수의 배수들은 전부 소수가 아니므로 배열에 false 처리
      if (prime[i]) {
         for (int j = i + i; j <= n; j += i) {
               prime[j] = false;
         }
      }
   }
}

 

시간복잡도는 O(Nlog(logN))입니다.