DESCRIPTION:
Count the number of divisors of a positive integer n.
Random tests go up to n = 500000.
Examples (input --> output)
4 --> 3 // we have 3 divisors - 1, 2 and 4
5 --> 2 // we have 2 divisors - 1 and 5
12 --> 6 // we have 6 divisors - 1, 2, 3, 4, 6 and 12
30 --> 8 // we have 8 divisors - 1, 2, 3, 5, 6, 10, 15 and 30
Note you should only return a number, the count of divisors. The numbers between parentheses are shown only for you to see which numbers are counted in each case.
function getDivisorCnt(n){
let result = [];
for(let i = 1; i <=n; i++){
if(Number.isInteger( n / i)) {
result.push(i);
}
}
return rsult.length;
}
라고 생각했는데, timeOut이 나버렸다.
O(n)의 복잡도를 갖고 있는데 될줄 알았다..
function getDivisorsCnt(n) {
let count = 0;
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
// i가 약수인 경우
if (n / i === i) {
// i가 n의 제곱근인 경우 (예: n이 25일 때, 5 * 5)
count++;
} else {
// i와 n / i가 둘 다 약수인 경우 (예: n이 12일 때, 2 * 6)
count += 2;
}
}
}
return count;
}
이렇게 작성하면 O(√n) 시간 복잡도의 시간복잡도를 갖는다.
감사합니다. 이런 정보를 나눠주셔서 좋아요.