약수 알고리즘 (Java)

 

N의 약수의 개수을 구하려면 어떻게 해야 할까?

방법 1

 

1부터 N까지 모든 수를 돌며 나누어 떨어지는 수의 개수를 더한다.

int N = 16;
int result = 0;

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

System.out.println(result);

 

총 N번을 반복하므로 O(N)의 시간복잡도를 가진다.

 

방법 2

 

N이 16일 때 약수는 1, 2, 4, 8, 16이 된다.

16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4의 규칙을 가진다.

 

다시 말하면 N의 약수 중 하나를 A라 하자.

그렇다면 N / A 또한 N의 약수가 돤다.

즉 N / A = A가 되므로 N = A^2이 되어 A = √N이 된다.

 

따라서 1부터 ~√N까지의 반복을 통해 N의 약수의 개수를 구할 수 있다.

 

int N = 16;
int result = 0;

for (int i = 1; i <= Math.sqrt(N); i++) {  // for (int i = 1; i * i <= N; i++)
    if (N % i == 0) {
        result += 2;
    } else if (N == i * i) {
        result += 1;
    }
}

System.out.println(result);

 

총 √N을 반복하므로 O(√N)의 시간복잡도를 가진다.

 

N까지의 모든 자연수의 약수의 합의 총합을 구하려면 어떻게 해야 할까?

방법 1

 

조금 더 응용된 방법으로 1부터 N까지의 약수의 총개수를 구해보자.

즉 N이 7이라면 1의 약수의 개수 + 2의 약수의 개수 + ... + 7의 약수의 개수의 합을 구하는 것이다.

 

위의 두 방식으로도 가능하지만 더 빠르게 구할 수 있는 방법이 있다.

바로 배수의 성질을 이용하는 것이다.

 

위의 사진을 참고해서 보면 좀 더 쉽게 이해할 수 있다.

 

7 이하의 자연수 중에서 1을 약수로 가지는 수의 개수: 7 (1,2,3,4,5,6,7) => [N/1]

7 이하의 자연수 중에서 2를 약수로 가지는 수의 개수: 3 (2, 4, 6) => [N/2]

7 이하의 자연수 중에서 3을 약수로 가지는 수의 개수: 2 (3, 6) => [N/3]

7 이하의 자연수 중에서 4를 약수로 가지는 수의 개수: 1 (4) => [N/4]

7 이하의 자연수 중에서 5를 약수로 가지는 수의 개수: 1 (5) => [N/5]

7 이하의 자연수 중에서 6을 약수로 가지는 수의 개수: 1 (6) => [N/6]

7 이하의 자연수 중에서  7을 약수로 가지는 수의 개수: 1 (7) => [N/7]

 

약수가 아닌 수들을 계산하지 않고 확실히 약수인 개수만 찾기 때문에 빠르게 구할 수 있다.

int N = 7;
int result = 0;

for (int i = 1; i <= N; i++) {
    result += (N / i);
}

System.out.println(result);

따라서 시간 복잡도는 O(N)이 된다.

 

방법 2

 

위의 방법은 한 번만 실행하기에는 무리가 없다.

하지만 테스트 케이스가 여러 개가 된다면 이미 했던 연산을 반복해야 한다는 단점이 있다.

예를 들면, 7 이하의 모든 자연수의 약수의 합의 총합을 구했다면 8 이하의 모든 자연수의 약수의 합의 총합을 구할 때 

7 이하의 모든 자연수의 약수의 합의 총합 + 8의 약수의 총합만 하면 된다.

 

이를 구현하기 위해 "에라토스테네스의 체"의 방법을 사용할 것이다.

 

위의 방법과 유사한 점이 많기 때문에 같은 사진으로 설명하겠다.

 

입력값의 최댓값이 N - 1이라 하자. 배열은 0부터 시작되므로 최댓값을 N - 1이라 했다.

1의 배수: index가 1, 1 * 2, 1 * 3, ... 1 * N인 배열의 값에 1 더하기

2의 배수: index가 2, 2 * 2 2 * 3, ... 2 *  N / 2인 배열의 값에 2 더하기

...

N의 배수: index가 N인 배열의 값에 N 더하기

 

이 과정을 거치면 dp배열에 해당 수에 따른 약수의 합이 저장된다.

하지만 우리는 주어진 수까지의 모든 약수의 총 합이 필요하므로 하나의 배수를 더하는 과정을 끝내게 되면 해당 값의 약수는 모두 구해졌으므로 해당 값 - 1까지의 총합 + 해당 값의 약수의 합을 더한다.

 

예를 들면, 3의 배수에 모두 3을 더해주고 나면 3까지의 자연수의 약수의 합들의 총합은 이미 구해진 상태이므로 2까지의 자연수의 약수의 합의 총합 + 3의 약수의 합을 해준다.

 

코드를 참고하면 이해가 더 쉬울 것이다.

final int maxN = 1000001;
long[] dp = new long[maxN];

for (int i = 1; i < maxN; i++) {
    for (int j = 1; i * j < maxN; j++) {
        dp[i * j] += i;
    }
    // i이하 수의 약수의 합들의 합 구하기
    dp[i] += dp[i - 1];
}

따라서 시간 복잡도는 O(NlogN)이 된다. (에라토스테네스의 체의 방법을 사용하긴 했지만 해당 방법은 소수를 찾기위한 알고리즘이므로 시간 복잡도가 다르다는 점 유의하자.)

 

추천 문제

17427번: 약수의 합 2

17425번: 약수의 합

 

 

Reference

https://brightmango.tistory.com/345