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