Lesson 10 - CountFactors

A positive integer D is a factor of a positive integer N if there exists an integer M such that N = D * M.

For example, 6 is a factor of 24, because M = 4 satisfies the above condition (24 = 6 * 4).

Write a function:

class Solution { public int solution(int N); }

that, given a positive integer N, returns the number of its factors.

For example, given N = 24, the function should return 8, because 24 has 8 factors, namely 1, 2, 3, 4, 6, 8, 12, 24. There are no other factors of 24.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

---

내 답안

그냥 나눠지는 숫자를 센다. 퍼포먼스에서 실패

class Solution {
    public int solution(int N) {
        int numberOfFactors = 0;

        for(int i=1; i<=N; i++) {
            if (N % i == 0) {
                numberOfFactors++;
            }
        }

        return numberOfFactors;
    }
}

---

베스트 답안

인수를 구하는 알고리즘이 있다.

100의 제곱근은 10인데 10의 인수를 생각하면 1, 2, 5, 10이 구해진다.

이 수로 100을 나누면 몫은 다음과 같다.

100 / 1 = 100
100 / 2 = 50
100 / 5 = 20
100 / 10 = 10

즉 정수 N의 제곱근의 인수로 나눈 경우의 몫도 인수가 된다.
이때 10은 중복이 되므로 카운트 할 필요 없다.

이를 코드로 나타내면 아래와 같이 된다.

class Solution {
    public int solution(int N) {
        int count = 0;

        for(int i=1; i<=Math.sqrt(N); i++) {
            if (N % i == 0) {
                count++;

                if(N / i != i) {
                    count++;
                }
            }
        }

        return count;
    }
}