[알고리즘] 에라토스테네스 체

1부터 자연수 N까지의 소수를 확인할때 사용하기 용이한 공식이다. 

 

이중반복문을 피하여 소수를 구할 수 있기 때문에 효율성에서 많은 이점이있다. 

 

자연수 N+1의 크기를 가지는 배열을 만들어 2부터 반복문을 실행하여 

배열의 데이터가 0(소수)라면 해당 수의 배수를 모두 1로 변경하여 소수에서 제외 시킨다. 

 

ex) 자연수 N 까지의 소수의 총 개수를 구한다.

public static int solution(int n) {
    int[] arr = new int[n+1];
    int answer = 0;
    for (int i = 2; i <= n; i++) {
        if(arr[i] == 0) {
            answer++;
            for (int j = i; j <=n; j =j +i) {
                arr[j] = 1; // j=j+i(j의 배수) 
            }
        }
    }
    return answer;
}