[Javascript] Codility Lesson10 - CountFactors

 

https://namu.wiki/w/JavaScript

 

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

 

문제 요약

• N = D * N 이 성립하면 D는 N의 인수다.
• N이 주어졌을 때 N의 인수 개수를 구하여라
• N의 범위는 1 ~ 2,147,483,647이며, N과 D는 자연수이다.

 

풀이

function solution(N) { 
    let result = 0;
    const M = Math.sqrt(N);
    let sqrtInt = Math.floor(M);

    while (sqrtInt > 0) {
        let remain = N % sqrtInt;
        result = remain === 0 ? result + 1 : result;
        sqrtInt--;
    };

    result = Number.isInteger(M) ? result * 2 - 1 : result * 2

    return result;
};

 

https://app.codility.com/

1) N이 10일 때 인수 : 1, 2, 5, 10

2) N이 12일 때 인수: 1, 2, 3, 4, 6, 12

3) N이 16일 때 인수: 1, 2, 4, 8, 16

 

1)~ 3) 까지의 케이스를 통해, N의 제곱근 M을 구한 뒤 1 ~ M 에서 N의 인수를 모두 찾고 2를 곱하면 되는 것을 알 수 있다. (M이 정수면 곱하기 2를 해준 값에서 -1을 한다.) 시간 복잡도는 O(sqrt(N))이 나왔다.