[Codility - Java] 10. Prime and composite numbers - 1. CountFactors

CountFactors

• Prime number
  • 소수
  • 1보다 큰 자연수이면서, 1과 자기 자신만을 약수로 가지는 수
• Composite number
  • 합성수
  • 1보다 큰 자연수이면서, 소수가 아닌 수
• Divisor, Factor
  • 약수
  • 어떤 수를 나누어 떨어지게 하는 수

---

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].

---

N = D * M을 만족하는 정수 M이 존재한다 할때, 양수 D는 양수 N의 약수입니다.
6은 24의 약수

주어진 자연수 N의 약수를 반환하는 문제

1 <= N <= 2^31 - 1 int 자료형의 표혐범위를 넘어서는 부분에 대한 신경을 써야 합니다.

---

대칭 약수를 이용하여 문제를 이용하면 $O(\sqrt{n})$ 시간복잡도로 문제를 해결할 수 있습니다.
i를 1부터 증가시키면서, 제곱수가 N보다 작으면서 i가 N의 약수인지를 확인합니다.(N % i == 0 을 만족하면 i는 N의 약수)
만일 i가 약수일 경우 2개를 result에 합산합니다.(i와 i의 대칭약수인 N / i)

i의 제곱이 N보다 커질 경우 반복문을 종료하지만, i * i == N일 경우에는 result에 1을 더 추가해야합니다 (N = 36일 경우, 6)

이때, N이 int 자료형의 Max값일 경우, i * i를 연산하는 부분에서 overflow 현상이 일어날 수 있습니다.
때문에 i의 자료형은 long타입으로 설정해야 합니다.

static int countFactors(int N) {
    int result = 0;
    long i = 1;
    while (i * i < N) {
        if(N % i == 0)
            result += 2;
        i++;
    }
    if (i * i == N) {
        result++;
    }
    return result;
}

$O(\sqrt{n})$

---

codility 결과