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)

     

    반응형

    댓글