소수 판별법 (낱개의 숫자에 대하여, 에라토스테네스의 체) Java

1. 하나의 숫자에 대한 소수 판별

(1) 방법

판별해야할 숫자를 N이라고 하면 다음과 같은 방법으로 N이 소수인지 여부를 판별할 수 있다.

int N = Integer.parseInt(br.readLine());

for(int i = 2; i<= Math.sqrt(N); i++){
    if(N%i == 0) System.out.println("소수가 아닙니다.");
    return;
}
// 2이상 √N이하의 모든 수에 대해서 나누어 떨어지지 않았다면, 
System.out.println("소수 입니다.");

(2) 왜 √N까지만 확인하면 되나요?

예를 들어서 설명해보겠다. N == 64라면,

√N은 8이다.

ab = 64라면  √N 은 8*8 처럼 a와 b가 같은 수이다.
만약 a < 8이 된다면, b는 곱한 결과가 64가 되기 위해서 a가 줄어든 만큼 배로 커져야 한다.
따라서 a < √N 이 되면 반자동적으로 b > √N 이 된다.

따라서 만약에 특정 수 N에 대하여 2 ~ √N까지의 수 중에 나누어 떨어지는 수가 없다면, √N보다 큰 수 중에서도 나누었을 때, 나누어 떨어지는 숫자가 없다는 말이다.
왜냐하면 2 ~ √N의 수 중 N을 나누었을 때, 나누어 떨어지는 a란 수가 있다면, 그 파트너인 b는 무조건 √N보다 커야하기 때문이다. 반대로 √N ~ N-1 중에 N을 나누었을 때, 나누어 떨어지는 숫자가 있다면, 그 파트너는 무조건 2 ~ √N-1 안에 있어야 한다. 하지만 2 ~ √N-1 중에 나누어 떨어지는 숫자가 없으므로 자동적으로 그 반대편에도 나누어 떨어지는 수가 없다. (파트너 관계가 충족되지 않기 때문이다.)

2. 특정 범위 내의 숫자들 소수 판별 - '에라토스테네스의 체' 이용

(1) 방법

해당 방법은

1. 특정 숫자들의 구간을 배열로 나타내고,
2. 배열 내의 소수가 아닌 숫자들을 지워서
3. 진짜 소수만 남기는

방식의 소수 판별법이다.
겉보기에는 시간이 O(N√N) 정도 들 것 같지만, 에라토스테네스의 체를 이용하면 시간복잡도는 O(NloglogN)으로 압도적으로 줄어든다.

에라토스테네스의 체 방법은 다음과 같다.

출처: 위키피디아

0. 소수는 true, 소수가 아닌 수는 false라고 해보자. (배열의 defalut 값은 true)
   1. 2를 조회했을 때, true라고 나온다. 따라서 2는 소수이다. 2의 배수는 소수가 아니므로 모두 false로 바꾼다.
   2. 3를 조회했을 때, true라고 나온다. 따라서 3은 소수이다. 3의 배수는 소수가 아니므로 모두 false로 바꾼다.
   3. 4는 2의 배수로 이미 false처리가 되었기 때문에 넘어간다.
   4. 5는 조회했을 때, true라고 나온다. 따라서 5은 소수이다. 5의 배수는 소수가 아니므로 모두 false로 바꾼다.

만약 주어진 구간이 0 ~ 120까지이면, 11*11 = 121이므로 2~10 내의 소수 2,3,5,7만 확인하면 된다. 코드로 나타내면 다음과 같다.

int N = Integer.parseInt(br.readLine);
boolean [] isPrime = new boolean [N];

// default 값 true로 바꾸기
for(int i = 0; i< isPrime.length; i++){
    isPrime[i] = true;
}

// 소수 판별 -> 소수가 아닌 값들은 false로 바뀐다.
for(int i = 2; i*i <= N; i++){
    if(isPrime[i]){
        for(int j = i*i; j <= N; j += i){
            // 소수의 배수들은 모두 false 처리
            isPrime[j] = false;
        }
    }
}

(2) 왜 i*i <= N 인 i까지만 계산하면 되나요?

위의 예시 처럼 N == 120이라고 해보자. 1111 = 121로 120을 넘는다. 11의 다른 배수들은 11보다 작은 소수를 처리하며 전부 false 처리가 되었다.
ex) 11 * 짝수 = 2의 배수에서 전부 처리, * 3,6,9 = 3의 배수에서 처리 등.
따라서 만약 처리가 필요하다면, 2,3,5,7 그 다음 소수인 11의 배수에 대한 처리인데, 이는 내가 구하려는 값의 범위를 넘었음으로 안해도 된다.