[프로그래머스] 소수 구하기 (JavaScript)

 

문제 출처

문제 요약

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어 지는 수를 의미합니다.(1은 소수가 아닙니다.)

문제 풀이

1번째

function solution(n) {
  let count = 0;
  for (let i = 2; i <= n; i++) {
    let 소수 = true;
    for (let j = 2; j < i; j++) {
      if (i % j === 0) {
        소수 = false;
      }
    }
    if (소수) ++count;
  }
  return count;
}

• 단순한 방법. N(O*2) 주어진 수 까지 나누면서 소수를 구한다.
• 당연히 타임 아웃

2번째

function solution(n) {
  const 소수들 = [2];
  for (let i = 2; i <= n; i++) {
    const is소수 = 소수들.some((c) => i % c === 0);
    if (!is소수) 소수들.push(i);
  }
  return 소수들.length;
}

• 소수들로 나누어서 떨어지면 소수가 아니기 때문에 루프를 돌면서 소수만을 구한다.
• 그래도 타임 아웃

3번째

function solution(n) {
  const 소수들 = new Array(n).fill(true);
  소수들[0] = false;
  for (let i = 2; i ** 2 <= n; i++) {
    if (소수들[i - 1] === true) {
      for (let j = i ** 2; j <= n; j += i) {
        소수들[j - 1] = false;
      }
    }
  }
  return 소수들.filter((e) => e).length;
}

• 에라토스테네스의 체를 이용한 방법
• 주어진 값까지 루프를 돌면서 소수의 배수를 먼저 제거한다.

4번째

//위와 같은 원리
function solution(n) {
  const s = new Set();
  //짝수는 소수 일수가 없음
  for (let i = 3; i <= n; i += 2) {
    s.add(i);
  }
  s.add(2);
  for (let j = 3; j ** 2 < n; j++) {
    if (s.has(j)) {
      for (let k = j ** 2; k <= n; k += j) {
        s.delete(k);
      }
    }
  }
  return s.size;
}

• Set을 이용한 풀이 성능 상은 거의 동일할 듯 하다.

결론

에라토스테네스의 체 라는 것을 이해해야 하는 수학적 문제이다.

소수를 구하기보다는 소수가 아닌 것을 제외하면 되고 그건 소수들의 배수를 제거하면 된다.