[알고리즘] 소수 구하기

소수란?

소수: 1과 자기 자신만을 약수로 갖는 수.

예시

3의 약수는 1과 3이므로 소수이다.
11의 약수는 1과 11이므로 소수이다.

그렇다면 1은 어떨까?

1은 소수일까?

결론부터 말하자면 1은 소수가 아니다.

소수가 되려면 약수가 2개 있어야 하는데 1은 약수가 하나이므로 소수가 될 수 없다.

제곱근이란?

제곱근(square root): 어떤 수의 제곱값을 만들어내는 숫자.

예시

2 * 2 = 4 이므로, 4의 제곱근은 2이다.

---

소수와 제곱근

소수를 구하기 위해선 제곱근까지만 확인하면 된다.

why?

예를 들어 보자.

어떤 수 n이 소수인지 확인하려고 한다.

n = 28이라면,

28의 약수는 1, 2, 4, 7, 14, 28이 있다.
약수는 좌, 우의 개수가 대칭되게 존재한다.

즉, 28이 2로 나누어 떨어지면 14로도 나누어 떨어지고, 4로 나누어 떨어지면 7로도 나누어 떨어진다.

그리고 28의 제곱근은 5.2915...으로 5보다 크지만 6보다 작다.

그렇다면, 28을 28의 제곱근 이하로 나누었을 때, 나누어 떨어진다면, 제곱근 보다 큰 숫자도 약수가 된다는 뜻이므로 소수가 아니다.
반대로 28을 28의 제곱근 이하로 나누었을 때 나누어 떨어지지 않으면 제곱근 보다 큰 숫자도 약수가 안 된다는 뜻이므로 소수이다.

그러므로 제곱근 이하의 수만 약수인지 확인하면 소수를 판단할 수 있는 것이다.

이 원리를 이용하면 효율적으로 소수를 구하는 코드를 짤 수 있다.

코드 예시

public class PrimeCheck {
    // 소수 판별 함수
    public static boolean isPrime(int n) {
        if (n <= 1) return false;  // 1은 소수가 아님
        if (n == 2) return true;   // 2는 소수

        // 2부터 sqrt(n)까지 나누어보며 소수 판별
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;  // 나누어떨어지면 소수가 아님
            }
        }

        return true;  // 나누어떨어지지 않으면 소수
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5, 16, 17, 18, 19, 25, 29};

        for (int num : numbers) {
            if (isPrime(num)) {
                System.out.println(num + " is a prime number.");
            } else {
                System.out.println(num + " is NOT a prime number.");
            }
        }
    }
}

추가

Math.sqrt()는 제곱근을 구하는 자바의 내장 함수이다.