모든 수의 약수 개수 찾기(1초이내)

Seok-Hyun Lee·2020년 7월 22일
1

코드 조각

목록 보기
3/4

N 까지의 자연수들의 약수 개수

예) 1부터 8까지 자연수들의 약수들을 나열해보자

자연수 : 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 초 이내 연산이 안된다

최적화

Bottom-up

약수의 개수를 구하는 것을 범위내의 배수의 개수를 구하는 것으로의 역발상

[자연수]
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 을 해줌으로써 약수를 찾기 위한 탐색 횟수를 극히 줄인 방법이다.

profile
Arch-ITech

0개의 댓글