Programmers, 합성수 찾기

20/12/2022 #algorithm #programmers #level0
# Level 0. 합성수 찾기

합성수 찾기

문제 설명

약수의 개수가 세 개 이상인 수를 합성수라고 합니다. 자연수 n이 매개변수로 주어질 때 n이하의 합성수의 개수를 return하도록 solution 함수를 완성해주세요.

제한사항

첫번째 풀이

1
2
3
4
5
6
7
8
9
10
11
12
const solution = (n) => {
  let answer = 0;
  for (let i = 4; i <= n; i++) {
    for (let j = 2; j <= Math.floor(Math.sqrt(i)); j++) {
      if (i % j === 0) {
        answer++;
        break;
      }
    }
  }
  return answer;
};

두번째 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const solution = (n) => {
  const screener = new Array(n + 1).fill(false);
  for (let i = 2; i <= Math.floor(Math.sqrt(n)); i++) {
    if (screener[i]) continue;

    let multiplier = 2;
    while (i * multiplier <= n) {
      screener[i * multiplier] = true;
      multiplier++;
    }
  }

  return screener.filter((result) => result).length;
};