소수(Prime Number) 판별 방법 세 가지

소수(Prime Number)

"소수는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수"

 

즉, 소수는 1과 자기 자신만을 약수로 갖고있다. 

만약 1 보다 크고 자기 자신보다 작은 자연수를 약수로 갖게 된다면 이는 합성수라고 한다.

 

이제부터 어떤 수 N에 대하여 소수인지 판별하는 세 가지 방법을 정리하겠다.

 

방법 1.

" N 보다 작은 자연수들로 일일히 나누어 본다 "

 

2 부터 N-1 까지의 모든 자연수들로 나누어보았을 때

나누어 떨어지는 수가 없다면(즉, 1과 N 이외에 약수가 없다면) 그 수(N)는 소수에 해당할 것이다.

 

public class PrimalityTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println(isPrime(N));
    }

    public static boolean isPrime1(int n) {

        boolean isPrime = true;

        // 0과 1은 소수가 아니다
        if (n < 2) {
            return false;
        }

        for (int i = 2; i < n; i++) {
            // 1과 n 이외의 약수를 갖고 있는 경우
            if (n % i == 0) {
                isPrime = false;
                return isPrime;
            }
        }

        // 위 반복문에서 약수를 갖고 있지 않음이 확인되면 소수다
        return isPrime;
    }
}

 

 

방법 2.

" √N 이하의 자연수들로 모두 나눠본다 "

 

방법1 처럼 N 이하의 모든 자연수들로 나누어보면 의심의 여지 없이 소수 여부를 확인해볼 수 있지만 

생각해보면 굳이 그럴 필요 없이 √N 이하의 자연수들로만 나누어 보면 된다.

 

𝐍 = 𝑝 × 𝑞 ( 1 ≤  𝑝 , 𝑞 ≤ 𝐍 ) 라고 할 때, 

𝑝 와 𝑞  둘 중 적어도 하나는 √N 보다 작거나 같다.

 

예를 들어, 𝐍 = 16 이면

두 수의 곱으로 나타낼 수 있는 경우의 수는 아래와 같다.

 

1 × 16

2 × 8

4 × 4

8 × 2

16 × 1

 

𝑝가 증가하면 𝑞는 감소하는 꼴이다. (그 반대도 마찬가지이고)

그러므로 𝑝, 𝑞 둘 중 하나는 √N 보다 작거나 같다.

 

즉, √N 이하의 자연수 중(1은 제외) 나누어 떨어지는 수가 있다면 1과 N을 제외한 다른 자연수를 약수로 갖는다는 의미이므로 소수가 아니다.

 

public class PrimalityTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println(isPrime3(N));
    }

    public static boolean isPrime2(int n) {

        boolean isPrime = true;

        // 0과 1은 소수가 아니다
        if (n < 2) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            // 1과 n 이외의 약수를 갖고 있는 경우
            if (n % i == 0) {
                isPrime = false;
                return isPrime;
            }
        }

        // 위 반복문에서 약수를 갖고 있지 않음이 확인되면 소수다
        return isPrime;
    }

}

 

 

방법 3.

에라토스테네스의 체

" k=2 부터 √N 이하까지 반복하여 k를 제외한 k의 배수들을 제외시킨다"

 

k=2 이면, 4, 6, 8, 16, ... 을 제외

k=3 이면, 6, 9, 12, 15, ...을 제외

k=4 이면, 8, 12, 16, 20, ...을 제외

 

이렇게 k = √N 까지 반복을 마쳤을 때 제외되지 않고 남아 있는 수들이 소수이다.

 

public class PrimalityTest {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        System.out.println(isPrime3(N));
    }

    public static boolean isPrime3(int n) {

        boolean[] prime = new boolean[n+1];

        if (n < 2) {
            return true;  // false이면 소수. 1, 2번 방법과 반대로 표시
        }

        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (prime[i]) {
                continue;
            }

            for (int j = 2; i * j < n; j++) {
                prime[i * j] = true;
            }
        }

        return prime[n];
    }

}