[알고리즘] 효율적으로 소수를 구하는 방법 (Java 예제 포함)

소수란?

소수는 1과 자기 자신 외에는 약수가 없는 자연수입니다. 즉, 1과 자기 자신만으로 나누어떨어지는 숫자를 말합니다.

예시

• 2, 3, 5, 7, 11 등은 소수입니다.
• 4, 6, 8, 9, 10 등은 소수가 아닙니다. (다양한 약수를 가지고 있기 때문입니다.)

약수란?

약수는 어떤 수를 나누어떨어지게 하는 수를 의미합니다. 즉, 주어진 수를 나누었을 때 나머지가 0이 되는 수입니다.

예시

• 12의 약수: 1, 2, 3, 4, 6, 12

소수를 구하는 알고리즘

소수를 판별하기 위해서는 주어진 수가 약수를 몇 개 가지고 있는지 확인해야 합니다. 소수의 경우 약수가 1과 자기 자신만 있어야 합니다.

기본적인 소수 판별

다음 코드는 1부터 n까지의 모든 약수를 찾는 방법을 사용한 소수 판별 방법입니다.

public class Main {
    public static void main(String[] args) {
        int n = 12; // 소수를 판별할 숫자
        boolean isPrime = true; // 초기값은 true로 설정

        // 1부터 n까지 반복하여 n의 약수를 찾음
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                System.out.print(i + " "); // 약수를 출력
            }
        }
    }
}

설명:

• 1부터 n까지 반복하여, n이 i로 나누어떨어지는지 확인합니다.
• 나누어떨어지면 약수입니다.

소수 판별 최적화

1. 기본 판별 알고리즘:
   • n이 2부터 n-1까지의 모든 수로 나누어지는지 확인합니다.
   • 시간이 많이 소요될 수 있습니다.
2. 최적화 방법:
   • n의 제곱근까지만 반복해도 소수 판별이 가능합니다. 왜냐하면, 어떤 약수가 n의 제곱근보다 크면, 대응하는 약수는 제곱근보다 작기 때문입니다.

public class Main {
    public static void main(String[] args) {
        int n = 12; // 소수를 판별할 숫자
        boolean isPrime = true; // 초기값은 true로 설정

        // 2부터 n의 제곱근까지 반복하여 n의 약수를 찾음
        for (int i = 2; i < (int)Math.sqrt(n) + 1; i++) {
            if (n % i == 0) {
                isPrime = false; // 약수를 찾았으므로 소수가 아님
                break;
            }
        }

        if (isPrime) {
            System.out.println("소수입니다.");
        } else {
            System.out.println("소수가 아닙니다.");
        }
    }
}

설명:

• 제곱근을 사용하는 이유는, 만약 n이 a와 b로 나누어떨어진다면, a와 b 중 하나는 반드시 제곱근 이하이기 때문입니다.
• 예를 들어, 16의 제곱근은 4입니다. 2부터 4까지 반복하여 16이 소수인지 확인할 수 있습니다.