[알고리즘] 에라토스테네스의 체 in JS(Refactoring)

기존 작성한 알고리즘에서 최적화가 되지 않아 시간이 더 걸리는 문제를 발견했고 이를 수정합니다.

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

 

function primeNumberSieve(n) {
  const area = new Array(n + 1).fill(false);
  const result = [];

  // i <= n to i*i <= n
  // 주어진 합성수 n은 a*b의 형태로 존재하는데,
  // 이때 a와 b 중 하나는 반드시 n^(1/2)이하이다.
  for (let i = 2; i*i <= n; i++) {
    if (area[i]) continue;
	
    // i*2 to i*i
    // i*2~i*(i-1)까지는 이미 지워졌기 때문이다.
    for (let j = i * i; j <= n; j += i) {
      area[j] = true;
    }
  }

  area.forEach((flag, index) => {
    if (index > 1 && !flag) {
      result.push(index);
    }
  });

  return result;
}

const result = primeNumberSieve(10);
console.log(result);
// [2, 3, 5, 7]

 

console.time()과 console.timeEnd()를 이용해 간단하게 시간을 계산해 본 결과 최적화가 된 것으로 확인할 수 있습니다.

• primeNumberSieve(100)
  • 기존: 0.080078125 ms
  • 최적화: 0.072021484375 ms
• primeNumberSieve(10000)
  • 기존: 0.821044921875 ms
  • 최적화: 0.741943359375 ms
• primeNumberSieve(100000)
  • 기존: 4.073974609375 ms
  • 최적화: 3.486083984375 ms