[알고리즘] 에라토스테네스의 체 사용 이유

백준 1644번 문제를 풀다가 여러 소수를 구해야 하는 과정이 있었는데, trial division 방식으로 isPrime 함수를 만들어 문제를 해결했습니다. 그런데 에라토스테네스의 체를 사용하는 방법이 더 효율적이라 왜 그런지 찾아보며 과거에 작성한 글에 대해 보충을 하겠습니다.

[알고리즘] 에라토스테네스의 체(소수 판별)

▲과거 작성된 글

 

에라토스테네스 체는 한 번 동작시키는 것으로 2~n까지의 모든 소수를 구할 수 있습니다. 그에 따라 범위 내에 원하는 소수 리스트가 필요한 경우 사용하기에 적합합니다. 하지만 범위가 커지면서 메모리 사용이 커진다는 단점이 있습니다. 그렇기에 단일 소수 판별에는 부적합합니다.

 

trial division 방식의 경우 구현하기 쉽고, 메모리를 적게 사용한다는 장점이 있습니다. 많은 수를 판별하기 않고, 적은 수에 대한 소수 판별에 적합합니다. 그렇지만 많은 수 또는 큰 수에 대해서는 내부 반복문의 반복 횟수가 증가하기 때문에 느려질 수 있습니다.

 

백준 1644번에서 두 가지를 사용한 결과를 보여드리겠습니다.

trial division을 사용한 경우

에라토스테네스의 체를 사용한 경우

결과를 보면 에라토스테네스의 체를 사용한 경우에 시간이 크게 감소했음을 확인할 수 있습니다.

 

추가적으로 과거에 작성된 isPrime 함수에서 최적화가 덜 된 부분을 최적화하고 해당 결과를 보여드리며 마무리하겠습니다.

function isPrime(num) {
  if(num == 0 || num == 1) return false;
  if(num == 2) return true;
  if(num % 2 == 0) return false;
  
  // 해당 for문의 범위에 대한 설명은 전 글에 있습니다.
  // for(let i = 3; i <= Math.sqrt(num); i++) {
  // 위에서 조건문을 통해 2의 배수가 넘어오는 것을 차단했기 때문에
  // i를 1이 아닌 2씩 늘려 홀수만 확인하면 됩니다.
  for(let i = 3; i <= Math.sqrt(num); i+=2) {
    if(num % i == 0) return false;
  }
  
  return true;
}

isPrime 함수 최적화한 경우

 

최적화를 통해 시간이 단축되었지만, 에라토스테네스의 체 알고리즘보다 느린 것을 확인할 수 있습니다. 그렇기에 최종적으로는 여러 숫자의 소수 판별 또는 소수 리스트가 필요한 경우 사용하고, trial division의 경우 단일 숫자 또는 소수 판별 횟수가 적은 경우에 사용하는 것이 적합합니다.