소수 구하는 방법

소수는 1과 자기 자신 외에는 나누어 떨어지지 않는 숫자를 의미합니다. 소수는 암호학, 컴퓨터 과학, 수학 등에서 중요한 역할을 하며, 이를 구하는 다양한 알고리즘이 있습니다. 이 글에서는 소수를 구하는 세 가지 방법을 소개하고, 각각의 성능과 특징을 비교해 보겠습니다.

 

---

 

1. 기본 방법 (완전 탐색)

 

가장 직관적인 방법으로, 각 숫자에 대해 2부터 해당 숫자까지의 모든 수로 나누어 떨어지는지 확인하는 방식입니다. 이 방식은 이해하기 쉽지만, 숫자가 커질수록 비효율적입니다.

 

public static void method1() {
    for (int i = 2; i <= 1000; i++) {
      int n;
      for (n = 2; n <= i; n++) {
        if (i % n == 0) break;
      }
      if (n == i) {
        System.out.println(i);
      }
    }
}

 

설명:

• 2부터 1000까지의 숫자 중 소수를 출력합니다.

• 각 숫자 i에 대해 2부터 i까지 나누어 떨어지는지 확인하고, 나누어 떨어지지 않으면 소수로 간주합니다.

 

성능:

• 시간 복잡도는 O(n²)로 매우 비효율적입니다. 특히 숫자가 커질수록 나누어야 할 숫자가 많아집니다.

 

2. 제곱근까지만 확인하는 방법

소수 판별을 효율적으로 하기 위해, 숫자의 약수는 항상 제곱근을 기준으로 대칭을 이루는 특성을 이용할 수 있습니다. 즉, 어떤 수 n이 소수인지 확인하려면, 그 수의 제곱근까지만 나눠 떨어지는지 확인하면 됩니다.

 

public static boolean method2(int num) {
    if (num < 2) {
      return false;
    }

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

 

설명:

• Math.sqrt(num) 함수를 사용하여 num의 제곱근까지만 나누어 떨어지는지 확인합니다.

• 제곱근 이상의 약수는 그 이하의 약수와 대칭을 이루므로 더 이상 확인할 필요가 없습니다.

 

성능:

• 시간 복잡도는 O(n√n)으로, 기본 방법에 비해 훨씬 효율적입니다.

 

3. 에라토스테네스의 체 (Sieve of Eratosthenes)

에라토스테네스의 체는 대량의 소수를 빠르게 구할 수 있는 매우 효율적인 알고리즘입니다. 이 알고리즘은 소수의 배수를 제거하는 방식으로 작동하며, 남아있는 숫자는 모두 소수입니다.

 

public static void method3() {
    int limit = 1000;
    boolean[] isPrime = new boolean[limit + 1];

    for (int i = 2; i <= limit; i++) {
      isPrime[i] = true;
    }

    for (int i = 2; i * i <= limit; i++) {
      if (isPrime[i]) {
        for (int j = i * i; j <= limit; j += i) {
          isPrime[j] = false;
        }
      }
    }

    for (int i = 2; i <= limit; i++) {
      if (isPrime[i]) {
        System.out.println(i);
      }
    }
}

 

설명:

• 2부터 시작해, 해당 숫자의 배수를 제거하는 방식으로 동작합니다.

• i * i부터 배수를 제거하는 이유는 그보다 작은 배수들은 이미 처리되었기 때문입니다.

• 소수의 배수는 모두 제거되고, 남아 있는 수들은 소수입니다.

 

성능:

• 시간 복잡도는 O(n log log n)으로, 매우 효율적인 알고리즘입니다. 특히 큰 범위의 소수를 구할 때 효과적입니다.

 

 

정리

알고리즘	시간 복잡도	특징
기본 방법	O(n²)	단순하지만 비효율적
제곱근 방법	O(n√n)	효율적이며 간단한 소수 판별법
에라토스테네스의 체	O(n log log n)	매우 효율적, 대량의 소수를 구할 때 유용