0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다.

알고리즘 중에 그나마 쉬운 편에 속한다.

 

 

(1) 우선 0과 1은 소수가 아니기때문에 제외한다.

(2) 소수인 2를 제외한 2의 배수를 모두 제외한다.

(3) 소수인 3을 제외한 3의 배수를 모두 제외한다.

(4) 소수인 5를 제외한 5의 배수를 모두 제외한다.

(5) 소수인 7을 제외한 7의 배수를 모두 제외한다.

(6) 위의 과정을 반복하며 제외되지 않은 소수 n을 제외한 n의 배수를 제외.. 무한 반복

 

 

글로만 읽어도 그럭저럭 이해가 되겠지만 아래의 친절한 그림을 보고나면 더욱 와닿을 것이다.

 

 

출처 <wikipedia>

 

 

이 알고리즘을 JAVA로 작성해보자.

 

    public static String test(int num) {
    // 인자로 제공되는 수와 인덱스 넘버를 맞춰야하기 때문에 +1
    // -> 140이 인자로 들어왔을 때 boolean[num]의 마지막 인덱스는 boolean[139]이다.
        boolean[] booleans = new boolean[num + 1];
    // 0과 1은 소수가 아니기 때문에 먼저 제외한다.
    // n의 배수는 소수가 아니다~ 식으로 제하고 남는 수를 소수로 지정하는 것이기 때문에
    // boolean의 기본값이 false이므로 소수가 아닌 수는 true로 지정해주고 false인 
    // 인덱스만 반환 받아 소수를 구하는 방식
        booleans[0] = booleans[1] = true;
        
        // 소수만 담을 배열 생성
        // 소수가 몇 개인지 미리 알 수 없기 때문에 Array가 아닌 List를 사용한다.
        // 중간의 값을 수정할 일이 없고 빨리 읽는 것이 중요하기 때문에 LinkedList가 아닌 ArrayList
        ArrayList<Integer> results = new ArrayList<>();


        // i는 소수다.
        // i*(i보다 작은 수)에 대한 배수 체크는 이미 이전에 모두 끝났기 때문에(i*j)
        // i*i가 인자로 들어온 숫자보다 크다면 연산할 이유가 없다.
        for (int i = 2; i * i <= num; i++) {
            if (!booleans[i]) { // 소수로 지정되어 있는 값일 경우(기본값일 경우)
                for (int j = i * i; j <= num; j+=i) {
                // 소수를 제외한 해당 값의 배수는 모두 소수에서 제외된다.
                    booleans[j] = true;
                }
            }
        }

        for (int i = 0; i < booleans.length; i++) {
            if (!booleans[i]) {
                results.add(i);
                // booleans의 index와 실제 수가 대응하고 있는 상태이기 때문에
                // false일 경우 index number를 배열에 삽입해준다.
            }
        }
        return results.toString();
    }

 

숫자만 보면 온 몸에서 알러지가 올라오는 사람도 이해하기 쉽도록 최대한 상세하게 적었는데 도움이 됐으면 좋겠다.