[Lv.0] 합성수 찾기 **

01수정·2022년 11월 14일

JavaScript algorithm programmers

프로그래머스 알고리즘

목록 보기

42/137

<입문 100문제> Day 11 - 수학, 반복문

문제

풀이

(1) 1 ~ n 순회

(2) (1) 을 순회하며 각각의 수에 대해 2 ~ (n-1) 순회하며 나누어 떨어지는 수가 있는지 체크.

(3) 합성수는 1, 자기자신, 또 다른 수, ... 에 의해 나누어 떨어지므로 위의 순회 중 하나라도 나누어 떨어지면 '합성수 배열'에 넣는다.

(4) 2 나 3으로 나누어 떨어지는 수 (6, 12)가 있으므로 '합성수 배열' 에는 동일한 수가 담겨 있으므로 [...new Set()] 으로 중복제거

function solution (n) {
    let compositions = []
    
    for (let i=1; i<=n; i++) {
        for (let j=2; j<i; j++) {
            if (i % j === 0) compositions.push(i)
        }
    }
    
    return [...new Set(compositions)].length;
}

해답

function solution(n) {
  const isPrime = num => {
    for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i === 0) return true;
    }
    return false;
  };

  let count = 0;

  for (let i = 1; i <= n; i++) {
    if (isPrime(i)) count += 1;
  }

  return count;
}