에라토스테네스의 체

에라토스테네스의 체

어느 수가 소수인지 판별하거나, 소수 한두개를 구할 때 보다는 범위 내에서 소수를 구하거나 대량으로 소수가 필요한 경우에 사용하면 좋은 알고리즘이다

방법

우선 원하는 범위 만큼의 배열을 만든 후

1. n부터 자기 자신을 제외한 모든 배수를 지운다 (1은 처음부터 제외, n = 2)

2. 배열에 숫자가 남아 있다면 n += 1시켜준 뒤에 다시 1을 반복한다

이게 끝이다

구현 1

const sieve = Array(size).fill(true);

for(let i=2; i<sieve.length;i++){
    for(let j=2;j*i<sieve.length;j++){
        sieve[j*i] = false;
    }
}

구하고자 하는 범위는 size로, 모두 true로 초기화한 배열 sieve를 선언한 뒤

첫 for문에서는 n을 1씩 늘리는 일을, 두번째 for문에서는 n의 배수를 지우는 일을 하고 있다

구현 2

어떤 수 n이 소수인지 판별할 때 우리는 2부터 n-1까지 n을 나누어 떨어지게 하는 수가 있는지 확인한다

그리고 시간 복잡도를 줄이기 위해서 n-1까지가 아닌 n의 제곱근까지만 해봐도 소수인지 판별할 수 있다

그것을 에라토스테네스의 체에도 적용이 가능하다

for(let i=2; i*i<sieve.length;i++){
    for(let j=2;j*i<sieve.length;j++){
        sieve[j*i] = false;
    }
}

구현 3

하다보니 두번째 for문도 살짝 마음에 들지 않았다 우선 가독하기 쉽게 코드를 수정해보자

for(let i=2; i*i<sieve.length;i++){
    for(let j=2*i;j<sieve.length;j+=i){
        sieve[j] = false;
    }
}

첫번째 for문에서 i를 1씩 늘리고 두번째 for문에서 i의 2배수를 지운 뒤 i를 한번씩 더 해주면서 3배,4배 수도 지우고 있는 걸 알 수 있다

하지만 잘 생각해보면 i를 2배수부터 지워나갈 필요가 없는 것을 알 수 있다 예를 들어

i가 2이라면 i*2, i*3, i*4... 를 지우고 --- a

i가 3이라면 i*2, i*3, i*4... 을 지운다 --- b

이미 a의 반복문에서 2의 배수를 다 지웠기 때문에 b반복문에서는 2의 배수부터 시작할 필요가 없는 것

for(let i=2;i*i<=sieve.length;i++){
    for(let j=i*i;j<sieve.length;j+=i){
        sieve[j]=false;
    }
}

이렇게 할 수 있다