자연수 : 1 2 3 4 5 6 7 8 => 약수개수 : 1 2 2 3 2 4 2 4
간단한 방법은 이중 for 문을 돌리는 방법이다.
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
if( i % j == 0 ) ...
}
}
하지만 이렇게 하면 자연수 n 이 30,000 정도 넘어가면 1 초 이내 연산이 안된다
약수의 개수를 구하는 것을 범위내의 배수의 개수를 구하는 것으로의 역발상
[자연수]
1 2 3 4 5 6 7 8
[약수]
1 : 1 1 1 1 1 1 1 1 <- 1의 배수이면 +1
2 : 1 2 1 2 1 2 1 2 <- 2의 배수이면 +1
3 : 1 2 2 2 1 3 1 2 <- 3의 배수이면 +1
4 : 1 2 2 3 1 3 1 3 <- 4의 배수이면 +1
5 : 1 2 2 3 2 3 1 3 <- 5의 배수이면 +1
6 : 1 2 2 3 2 4 1 3 <- 6의 배수이면 +1
7 : 1 2 2 3 2 4 2 3 <- 7의 배수이면 +1
8 : 1 2 2 3 2 4 2 4 <- 8의 배수이면 +1
즉, 이러한 개수를 담기 위한 배열을 미리 선언해두면 위의 이중 for 문이
int cnt[30001]; // 3만 이상
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j = j + i)
{
cnt[j] += 1;
}
}
이렇게 변한다.
즉, j 가 i 에서부터 시작하여 n 까지 i 의 배수마다 +1 을 해줌으로써 약수를 찾기 위한 탐색 횟수를 극히 줄인 방법이다.