[프로그래머스] 합성수 찾기.JS

https://school.programmers.co.kr/learn/courses/30/lessons/120846

나의 풀이

function solution(n) {
    let compositeNum = [];
    
    for (let i = 4; i <= n; i++) {
        let count = 0;
        for (let j = 1; j <= i; j++) {
            if (!(i % j)) count++;
        }
        if (count >= 3) compositeNum.push(i) ;
    }
    
    return compositeNum.length;
}

✔ 합성수는 4부터 시작
✔ dividend % divisor가 0인 경우 count 증가 -> count가 3 이상이면 합성수

참고할 만한 풀이

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;
}

✔ isPrime 함수 응용 -> 자기 자신과 1을 제외한 나머지 divisor가 존재 시 true

범위가 2 이상 Math.sqrt(num) 이하인 이유?

https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-number-to-determine-if-the-number-is

Math.sqrt(num)을 m으로 두고, ab = num 및 num이 소수가 아닐 때 (단, a >= 2, b >= 2)
1. a > m이면 b < m
2. a = m이면 b = m
3. a < m이면 b > m

공통점은 2 <= Math.min(a, b) <= m이라는 것.
따라서 isPrime 함수에서 num이 합성수라면 반드시 m 이하에서 1이 아닌 num의 약수를 얻을 수 있게 된다.