에라토스테네스의 체

프로그래머스에서 소수 찾기 문제를 풀다
작년 8월 쯤 친구로 부터 알게 된 에라토스테네스의 체 개념을 다시 공부하게 되었다.

에라토스테네스의 체

대량의 소수를 구할 때 반복문을 통해 모든 수에 접근하는 것이 아닌 소수로 판별된 값의 배수들을 모두 소수처리 해 모든 수에 접근하지 않고도 빠르게 소수를 구할 수 있는 방법이다.

예시

숫자 10의 소수를 구하라고 하면
기본적으로 반복문을 통해 소수여부를 판별할 수 있다.

for(let i=2; i<=10; i++){
    if(10%i === 0) {
      return false
    }
  return true

위와 같은 알고리즘을 사용할 경우 시간복잡도는 O(N)이다.
모든 경우의 수를 다 돌며 약수 여부를 판단하기 때문에 비효율적이다.
왜냐하면 예를 들어 8의 경우 24 = 42 인데 2와 4 모두 접근하기 때문이다.
이러한 경우 특정 숫자의 제곱근까지만 계산하면 O(N^(1/2))로 계산할 수 있다.

let num = Math.sqrt(10)
for(let i=2; i<=num; i++){
  if(10 % i){
    return false
  }
}
return true
}

더 나아가서 대량의 수에 대한 소수를 구하고자 한다면, 이 때 에라토스테네스의 체 개념을 사용하면 된다.
모든 수에 대한 소수를 구하지 않고 소수로 판별 된 값의 배수는 따로 소수 판별을 하지 않도록 한다.

let arr = []
for(let i=2; i<=10; i++){
  arr[i] = i
}
for(let j=2; j<=10; j++){
  if(arr[i] === 0) continue;
  for(let k=j*2; k<=10; k+=j){
    arr[k] = 0
  }
}