getDivisorCnt // codewars

samuel Jo·2023년 8월 6일
0

codewars

목록 보기
43/47

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) 시간 복잡도의 시간복잡도를 갖는다.

profile
step by step

1개의 댓글

comment-user-thumbnail
2023년 8월 6일

감사합니다. 이런 정보를 나눠주셔서 좋아요.

답글 달기