기본 알고리즘부터 풀어보는데에 있어서

이 소수를 구하는것에 상당히 애를 먹는다.

물론 소수 뿐만이 아니라 다른 유형의 문제들도

결국 머릿속에선 정리가 매우 잘되지만, 이걸 코드로 구현하는게 쉽지가 않다.

아무튼 각설하고, 소수를 판별하는 알고리즘에 대해 알아보도록 하자.

소수

소수는, 1보다는 큰 자연수들 중 1과 자기 자신만을 약수로 가지고 있는 수를 의미한다.

위키피디아의 이미지를 가져와보았다.

순서는 2부터 소수를 구하고자 하는 목표값 까지의 모든 수를 나열한다.

그다음 2는 소수기에 Prime Numbers에 2를 넣어준다.

그 다음 자기 자신을 제외한 2의 배수를 다 지운다.

지우는 이유?

자기 인수의 배수를 다 지우는 이유는 그 수들은 이미 배수라서 약수에 인수가 포함되기 때문이다.

이 구간을 계속 반복해주면 목표 수 사이까지의 소수가 구해지게 된다.

말로는 설명하기 어려운것 같다.

코드로 자세히 봐보도록 하자.

자바 코드로 구현하기

public class EratosTenes {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //여기서 N의 값을 9라고 해보자.
        int N = Integer.parseInt(br.readLine());
        
        boolean[] array = new boolean[N + 1]; // 배열은 0부터 시작하기 때문에 자릿수를 맞춰주는 개념으로 1을 더해주었다.
        
        //0과 1은 소수가 아니다.
        array[0] = true;
        array[1] = true;
        
        //2부터 시작해서 배열 총길이의 제곱근 값까지 반복한다.
        for(int i = 2; i <= Math.sqrt(array.length); i++) {
            if (array[i]) {
                continue;
            }
            
            // 소수가 아닌수를 true
            for(int j = i * i; j < array.length; j += i) {
                array[j] = true;
            }
        }
        
    }
}

이렇게하여 boolean[] array의 배열값에서 true이면 전부 소수가 아닌수가 된다.

여기서 true로 바꾸어주는 로직이 i * i로 시작하는 이유는

i의 처음 인수가 2이다. 근데 소수에서는 0과 1을 제외하면 2, 3까지는 무조건 소수임이 보장되어 있다.

그래서 i * i로 4부터 시작하여 자기 자신만큼을 더해주는게 배수의 원리이니까 전부 true로 바꿔주는게 된다.

이렇게 하여 소수를 구할 수 있게 된다.