숫자가 소수인지 아닌지 확인하는 Java 프로그램

 

소수의 기본 개념
소수(prime number)란 1과 자기 자신을 제외하고는 다른 어떠한 수로도 나눌 수 없는 자연수입니다. 자연수 중에서 1은 소수가 아니며, 2는 유일한 짝수 소수입니다. 

 

그 외의 소수들은 모두 홀수입니다. 예를 들어, 2, 3, 5, 7, 11, 13 등이 소수입니다. 소수는 암호학, 수학적 문제 해결, 소수의 분포를 연구하는 수론(Number Theory) 등의 다양한 분야에서 중요한 역할을 합니다.

소수 판별 알고리즘
숫자가 소수인지 아닌지 확인하는 문제는 간단해 보일 수 있지만, 입력되는 숫자가 클수록 연산 속도가 중요한 문제로 대두됩니다. 예를 들어, 단순하게 모든 숫자를 나눠보는 방식은 비효율적이기 때문에, 다양한 최적화 방법이 필요합니다. 

 

자바 프로그램을 사용해 소수 판별을 구현할 때 이러한 최적화 기법을 어떻게 적용할 수 있는지 알아보겠습니다.

1. 기본적인 소수 판별 방법
소수 판별을 위해 기본적으로 숫자 n에 대해 2부터 n-1까지 모든 수로 나눠 보고, 나누어 떨어지는 수가 있는지 확인할 수 있습니다. 만약 나누어 떨어지는 수가 하나라도 있다면 그 숫자는 소수가 아닙니다. 

 

하지만 이 방법은 매우 비효율적입니다. 예를 들어, n = 1000000과 같이 큰 수가 주어지면 2부터 999999까지의 수로 나누어야 하기 때문에 연산량이 기하급수적으로 증가합니다.

이 방법의 시간 복잡도는 O(n)입니다. 즉, 숫자가 커질수록 성능이 급격히 떨어집니다.

2. 제곱근을 이용한 최적화
숫자가 소수인지 확인할 때, 굳이 n-1까지의 모든 수로 나눌 필요가 없다는 사실이 중요합니다. 어떤 수 n의 약수는 항상 짝을 이루고 있기 때문에, 약수 중 작은 쪽이 √n 이하라는 점을 이용할 수 있습니다. 예를 들어, 숫자 36의 약수는 다음과 같습니다:

1 x 36
2 x 18
3 x 12
4 x 9
6 x 6
위의 예에서 보듯이 약수는 항상 두 수의 곱으로 나타나는데, 그중 작은 수는 반드시 √n보다 작거나 같습니다. 따라서 n이 소수인지 확인하기 위해서는 2부터 √n까지의 수로만 나눠보면 됩니다. 이 방법의 시간 복잡도는 O(√n)으로, 훨씬 더 효율적입니다.

3. 짝수 제외
소수 판별에서 추가적인 최적화 방법은 짝수에 대한 처리입니다. 2는 유일한 짝수 소수입니다. 따라서 2를 제외한 모든 짝수는 소수가 아닙니다. 이를 활용하면 2 외의 짝수는 검사하지 않아도 되므로 연산을 절반으로 줄일 수 있습니다.

자바 코드 상세 설명
이제 소수 판별 프로그램의 자바 코드에 대해 상세하게 설명드리겠습니다. 코드의 각 부분을 나누어 설명하며 그 동작 원리를 이해해 보겠습니다.

import java.util.Scanner;

public class PrimeCheck {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 사용자로부터 숫자를 입력받음
        System.out.print("소수인지 확인할 숫자를 입력하세요: ");
        int number = scanner.nextInt();
        
        // 소수 여부를 확인하는 함수 호출
        if (isPrime(number)) {
            System.out.println(number + "는 소수입니다.");
        } else {
            System.out.println(number + "는 소수가 아닙니다.");
        }
        
        scanner.close();
    }
    
    // 소수 여부를 확인하는 함수
    public static boolean isPrime(int num) {
        // 1은 소수가 아님
        if (num <= 1) {
            return false;
        }
        
        // 2는 유일한 짝수 소수
        if (num == 2) {
            return true;
        }
        
        // 짝수는 소수가 아님
        if (num % 2 == 0) {
            return false;
        }
        
        // 2부터 num의 제곱근까지 반복하며 소수 여부 확인
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

1. 사용자 입력 받기

Scanner scanner = new Scanner(System.in);
System.out.print("소수인지 확인할 숫자를 입력하세요: ");
int number = scanner.nextInt();

이 부분은 사용자로부터 숫자를 입력받는 코드입니다. Scanner 객체를 사용해 콘솔로부터 숫자를 입력받습니다. 이 숫자는 변수 number에 저장됩니다. 프로그램이 진행되면서 이 숫자가 소수인지 여부를 확인합니다.

2. 소수 판별 함수 호출

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

입력된 숫자를 소수인지 확인하는 isPrime() 함수를 호출합니다. 이 함수는 입력받은 숫자가 소수이면 true, 그렇지 않으면 false를 반환합니다. 반환된 값을 이용해 출력 결과를 결정합니다.

3. 소수 판별 함수

public static boolean isPrime(int num) {
    // 1은 소수가 아님
    if (num <= 1) {
        return false;
    }

    // 2는 유일한 짝수 소수
    if (num == 2) {
        return true;
    }

    // 짝수는 소수가 아님
    if (num % 2 == 0) {
        return false;
    }

    // 2부터 num의 제곱근까지 반복하며 소수 여부 확인
    for (int i = 3; i <= Math.sqrt(num); i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

이 함수는 소수 판별의 핵심입니다. 숫자가 소수인지 확인하는 여러 가지 조건들을 포함하고 있습니다.

1에 대한 처리: if (num <= 1) { return false; } 1은 소수가 아니므로, 입력된 숫자가 1 이하이면 false를 반환합니다.

2에 대한 처리: if (num == 2) { return true; } 2는 유일한 짝수 소수이므로, 입력된 숫자가 2이면 소수로 간주하여 true를 반환합니다.

짝수에 대한 처리: if (num % 2 == 0) { return false; } 2를 제외한 모든 짝수는 소수가 아니므로, 입력된 숫자가 짝수일 경우 false를 반환합니다.

제곱근을 이용한 소수 판별:

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

입력된 숫자가 홀수일 때, 3부터 해당 숫자의 제곱근까지의 모든 홀수로 나누어 봅니다. 만약 나누어 떨어지는 수가 있다면 소수가 아니므로 false를 반환하고, 그렇지 않다면 반복문이 끝난 후에 true를 반환하여 소수임을 판별합니다.

성능 최적화 방안
앞서 언급한 제곱근을 이용한 방법 외에도 추가적으로 성능을 최적화할 수 있는 방법이 있습니다. 예를 들어, 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하면 많은 숫자들에 대한 소수 여부를 한 번에 판별할 수 있습니다.