[java] 자바에서 사용하는 소수 판별 알고리즘

15 Dec 2023

java

소수(prime number)는 1과 자기 자신으로만 나누어떨어지는 수입니다. 소수를 판별하는 알고리즘은 다양한 방법으로 구현할 수 있습니다. 여기서는 자바에서 간단한 소수 판별 알고리즘을 언급하겠습니다.

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

에라토스테네스의 체는 주어진 범위 안의 모든 소수를 찾아내는 알고리즘으로, 주어진 범위의 모든 수에 대해 소수인지 여부를 판별하고 소수를 찾아냅니다. 이 알고리즘은 비교적 빠른 시간 안에 작은 수의 소수를 찾는 데에 유용합니다.

public class PrimeNumber {
    public static boolean isPrime(int number) {
        if (number <= 1) {
            return false;
        }
        for (int i = 2; i * i <= number; i++) {
            if (number % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int n = 17;
        if (isPrime(n)) {
            System.out.println(n + "은(는) 소수입니다.");
        } else {
            System.out.println(n + "은(는) 소수가 아닙니다.");
        }
    }
}

위의 예제는 주어진 숫자가 소수인지 판별하는 간단한 알고리즘을 자바로 구현한 것입니다.

에라토스테네스의 체 외에도 더 다양한 소수 판별 알고리즘이 존재합니다. 여러 알고리즘을 이용하여 소수를 효율적으로 판별할 수 있으니, 상황에 맞는 알고리즘을 선택하여 사용하면 됩니다.

더 많은 정보를 원하신다면, 다음 레퍼런스를 참고하세요.