Java, Kotlin] 에라토스테네스의 체

에라토스테네스의 체는 소수를 구하는 아주 기본적인 알고리즘이다.

알고리즘은 다음과 같다

1. 내가 원하는 수 만큼의 숫자를 깔아놓는다.

2. 0과 1은 소수가 아니므로 뺀다.

3. 2는 소수이고, 2의 배수부터는 소수가 아니므로 2를 제외한 2의 배수는 모두 빼버린다.

4. 3은 소수이고, 3의 배수부터는 소수가 아니므로 3을 제외한 3의 배수는 모두 빼버린다.

4. 4는 소수가 아니므로 넘어간다.

5. 5는 소수이므로 5의 배수부터는 ...

 

이걸 반복한다.

 

근데 가만히 생각해보자?

2의 소수라서 2*2 -> 2*3 -> 2*4를 뺐다.

3의 소수에서 3*2 .. 는 2의 배수에서 2*3으로 빼버렸지 않나.

그러므로 3*3부터, 즉 3^2부터 시작해도 된다.

5도 마찬가지로 5*2는 2의 배수에서, 5*3은 3의 배수에서, 5*4는 5*2*2 이므로 2의 배수에서 이전에 빼버렸으므로 5*5, 즉 5^2부터 소수 빼기를 시작해도 된다.

이 말인 즉슨, 이 배수 빼기는 제곱근까지만 빼버려도 된다는 의미가 된다. 예를 들어 121까지의 소수를 구한다 가정하면 11까지만 배수빼기를 해도 된다는 뜻이다. 11^2 = 121이기 때문에 어차피 최댓값이지 않은가.

 

이를 코드로 표현하면 다음과 같다. 자바와 코틀린으로 알고리즘 코드를 짰다.

 

-Kotlin

import kotlin.math.floor
import kotlin.math.sqrt

fun main(args: Array<String>) {
    question17103()
}

fun question17103() {

    // 최대크기만큼 체 준비. 배열은 0부터 시작하므로 최댓값 +1 로 배열 크기를 만드는 것을 잊지 않아야함.
    val eratosArray = Array(1000001) { true }
    //0과 1은 소수가 아니므로 뺀다.
    eratosArray[0] = false
    eratosArray[1] = false
    // 제곱근까지만 돈다.
    for(i in 2 .. floor(sqrt(eratosArray.size.toDouble())).toInt()) {
    	// 이전 배수빼기에서 살아남았으면, 이는 소수이다.
        if(eratosArray[i]) {
        	// 제곱근부터 돌며 소수의 배수값을 빼버린다.
            // step는 해당값만큼 올리는 코틀린의 for 문법이다. 자바의 마지막 i++ << 이걸 담당하는 곳임.
            for(j in i * i ..< eratosArray.size step i) {
                eratosArray[j] = false
            }
        }

    }
    
    // true로 살아남아 있는 배열의 위치가 소수이다.
}

 

- JAVA

import java.util.ArrayList;

class Solution {

    public int solution(int i) {
        
        int answer = 0;

        ArrayList<Boolean> solutionArray = new ArrayList<>();

		// true는 살아남은 값, false는 삭제된 값으로 가정한다.
		// 0과 1은 소수에서 제외한다.
        solutionArray.add(0, false);
        solutionArray.add(1, false);

		// 일단 전체를 소수로 가정한다.
        // 풀이로 치면, 1 ~ n 까지의 값을 깔아두는 것과 같다.
        for(int j = 2; j <= i; j ++) {
            solutionArray.add(j ,true);
        }

		// 앞서 말했다시피, 제곱근 값만 구하면 되기 때문에 j * j <= i; 로서 값을 줄일 수 있다.
        for(int j = 2; j * j <= i; j ++) {
        	// 만약 true라면 배수 제거 단계에서 사라지지 않았으므로, 소수로 간주하고 해당 값의 배수를 빼버린다.
        	// 해당 부분에서 4, 6 .. 뭐 이런 값들이 걸러진다.
            if(solutionArray.get(j)) {
            	// 해당 값의 배수를 빼버리는 로직이다.
                // j * j를 하는 이유는, 앞서 있는 j - 1의 값들이 전부 앞에서 미리 검사되기 때문인데,
                // ex. j가 2일때 2 + 2 + 2 + 2 + 2 를 미리 실행했기 때문에,
                //     j가 5일때 5 * 2 를 실행할 필요가 없는 것이다.
                // 다만, j * 2를 해도 효율성에서 걸리진 않는다(ㅋㅋ)
                // k += j 를 통해 j값을 꾸준히 더함으로서 배수를 구현, 배수를 전부 false로 만든다.
                for(int k = j * j; k <= i; k += j) {
                    solutionArray.set(k, false);
                }
            }
        }

		// true값을 찾아 소수값에 넣음
        for(int j = 0; j < solutionArray.size(); j ++ ) {
            if(solutionArray.get(j)) {
                answer += 1;
            }
        }

		
        return answer;
        
    }
}