Codility Lesson10. Prime and composite numbers - CountFactors ★

Tasks

https://app.codility.com/programmers/lessons/10-prime_and_composite_numbers/

내 풀이

function solution(N) {
    let ans = [];
    for (i=1; i<=N; i++) {
        if (N%i === 0) {
            ans.push(i)
        }
    }

    return ans.length ? ans.length : 0
}

역시 프로그래머스랑은 다르게 21억까지 N이 주어지니 시간 복잡도를 초과한다. 이럴 땐 제곱근을 활용하면 된다고 함

중요 더 빠른 약수 구하기 (Math.sqrt()활용)

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    const divisors = [];

    // N이 24일 때 1부터 4.xxxx까지 반복
    for (let i = 1; i <= Math.sqrt(N); i++) {
        // 1로 나누어지니 1push
        // 2로 나누어지니 2push
        // 3으로 나누어지니 3push
        // 4로 나누어지니 4push
        if (N % i === 0) {
            divisors.push(i);

            // 1은 24와 같지 않으니 24push
            // 2는 12와 같지 않으니 12push
            // 3은 8과 같지 않으니 8push
            // 4와 6은 같지 않으니 6push
            if (i !== N / i) {
                divisors.push(N / i);
            }
        }

        // 반복문을 다 돌았기에 나온 배열을 반환
    }
    return divisors.length ? divisors.length  : 0
}

반복문의 횟수를 줄이되, 정해진 양만큼을 순회할 수 있어 매우 빠름