11. 에라토스테네스의 체 (Sieve of Eratosthenes) Codility Lesson 한국어 정리본 (JavaScript ver.)

에라토스테네스의 체란?

에라토스테네스의 체(Sieve of Eratosthenes) 는 주어진 범위 내에서 모든 소수를 빠르게 찾는 알고리즘이다. 이 방법은 소수를 걸러내는 방식으로 동작하며, O(n log log n) 의 시간 복잡도를 가진다.

---

1. O(n log log n) 시간 복잡도의 소수 판별

JavaScript 코드:

function sieve(n) {
    let sieve = new Array(n + 1).fill(true);
    sieve[0] = sieve[1] = false;
    
    for (let i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (let k = i * i; k <= n; k += i) {
                sieve[k] = false;
            }
        }
    }
    return sieve;
}

이 방법을 통해 n 이하의 모든 소수를 찾을 수 있다.

---

2. 소인수 분해 (Factorization)

소인수 분해는 정수를 소수의 곱으로 표현하는 과정 이다.

JavaScript 코드:

function sieve(n) {
  // n까지의 모든 수에 대해, spf[i]를 i로 초기화
  const spf = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    spf[i] = i;
  }
  
  // 0과 1은 소수가 아님
  spf[0] = 0;
  spf[1] = 1;
  
  // 2부터 √n 까지의 수에 대해 최소 소인수를 업데이트
  for (let i = 2; i * i <= n; i++) {
    if (spf[i] === i) { // i가 소수라면
      for (let j = i * i; j <= n; j += i) {
        // 아직 j의 최소 소인수가 결정되지 않았다면, i로 설정
        if (spf[j] === j) {
          spf[j] = i;
        }
      }
    }
  }
  
  return spf;
}

function factorization(x) {
  // x에 대한 SPF 배열 생성
  const spf = sieve(x);
  const factors = [];
  
  // x가 1이 될 때까지 소인수로 나누기
  while (x !== 1) {
    factors.push(spf[x]);
    x = Math.floor(x / spf[x]);
  }
  
  return factors;
}

// 예시
console.log(factorization(24)); // 출력: [2, 2, 2, 3] (24 = 2 * 2 * 2 * 3)
console.log(factorization(60)); // 출력: [2, 2, 3, 5] (60 = 2 * 2 * 3 * 5)

이 방법을 사용하면 O(log x) 시간 복잡도로 소인수 분해가 가능하다.

 

소수만 출력하려면 아래 코드

function sieve(n) {
  const spf = new Array(n + 1);
  for (let i = 0; i <= n; i++) {
    spf[i] = i;
  }
  spf[0] = 0;
  spf[1] = 1;
  for (let i = 2; i * i <= n; i++) {
    if (spf[i] === i) { // i가 소수이면
      for (let j = i * i; j <= n; j += i) {
        if (spf[j] === j) {
          spf[j] = i;
        }
      }
    }
  }
  return spf;
}

function factorization(x) {
  const spf = sieve(x);
  const factorsSet = new Set(); // 중복 제거를 위한 Set 사용
  while (x !== 1) {
    factorsSet.add(spf[x]);
    x = Math.floor(x / spf[x]);
  }
  return Array.from(factorsSet);
}

// 예제 테스트
console.log(factorization(24)); // 출력: [2, 3] (24 = 2*2*2*3)
console.log(factorization(60)); // 출력: [2, 3, 5] (60 = 2*2*3*5)