(C언어)프로젝트 오일러(Project Euler)12.500개 이상의 약수를 갖는 가장 작은 삼각수는?

 

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.예를 들어 7번째 삼각수는
1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
이 삼각수들의 약수를 구해봅시다.
1: 1 
3: 1, 3 
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.
그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

 

#include <stdio.h>

int main()
{
	int n = 0, i, sum, count = 0;

	while (count < 500)
	{
		count = 0;
		n++;
		sum = n * (1 + n) / 2;

		for (i = 1; i * i <= sum; i++)
		{
			if (sum % i == 0)
				count += 2;
		}
		if (i * i == sum)
			count++;
		
	}
	printf("%d\n", sum);

	return 0;
}

삼각수(sum)를 n번쨰까지 구해나가고, 이를 1부터 sum까지 나눠보려면 시간이 너무 오래 걸린다. 처음에 그렇게 시도했다가 5~6분이 넘어도 프로세스가 작동 중이어서 포기했다.

 

좀 더 효율적으로 작동시키려고 약수를 구하는 알고리즘을 찾아보았다. 

 

중학생 때 "30의 약수를 구해보세요"라고 하면 1부터 시작하여 곱해서 30이 되는 수를 찾았다.

1*30, 2*15, 5*6 이렇게 말이다.

6*5는 의미가 없다. 6은 5*6에서 이미 약수임이 드러났기 때문이다.

이미 찾은 약수가 중복되어 발견되지 않는 마지노선이 바로 루트이다.

루트 30은 5.4 정도이다. 이 수를 넘어가면 6이라는 수를 중복해서 찾게 된다. 왜 그런지는... 모르겠다. 그렇다고 하니까 써먹자.

 

 

즉, 1부터 sum까지 다 나눠보지 않고 sum의 제곱근까지만 구해보면 된다. 약수 한 쌍을 찾는 과정이므로 count에 2를 더한다.

i*i == sum 이면 약수가 i,i란 소리인데 같은 수이니 count를 한 번만 더한다.

 

마지막에 sum을 출력하면 76576500이 출력된다.

 

프로젝트 오일러에서 제시하는 문제가 많은 수를 처리하게끔 하니 최적화가 안 되어있으면 한참이 걸리는 문제가 꽤 있다. 수학이나 알고리즘을 공부하는 사람이 확실히 유리한 것 같다.