69 lines
No EOL
1.3 KiB
C
Executable file
69 lines
No EOL
1.3 KiB
C
Executable file
#include <stdio.h>
|
|
|
|
// The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
|
|
|
|
// 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
|
|
|
|
// Let us list the factors of the first seven triangle numbers:
|
|
|
|
// 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
|
|
// We can see that 28 is the first triangle number to have over five divisors.
|
|
|
|
// What is the value of the first triangle number to have over five hundred divisors?
|
|
//first attempt 29 minutes, 40 seconds
|
|
//second attempt: 13 minutes, 32 seconds
|
|
|
|
int countDivisors(long long);
|
|
|
|
int main() {
|
|
int i = 1;
|
|
int j;
|
|
long long triNumber;
|
|
|
|
while(1) {
|
|
if(i % 500 == 0) {
|
|
printf("On iteration %d: \n", i);
|
|
}
|
|
//find the current tri number
|
|
triNumber = ((i + 1) * i) / 2;
|
|
i++;
|
|
if(triNumber % 2 == 1) continue;
|
|
|
|
int divisors = countDivisors(triNumber);
|
|
if(divisors > 200) {
|
|
printf("%lld (%d divisors)\n", triNumber, divisors);
|
|
}
|
|
|
|
|
|
|
|
if(divisors > 500) break;
|
|
if(i < 0) break;
|
|
}
|
|
|
|
printf("\n%lld", triNumber);
|
|
|
|
return 1;
|
|
}
|
|
|
|
int countDivisors(long long number) {
|
|
int i;
|
|
int divisors = 0;
|
|
|
|
for(i = 1; i * i <= number; i++) {
|
|
if(number % i == 0) {
|
|
divisors += 2;
|
|
}
|
|
}
|
|
|
|
if(i * i == number) {
|
|
divisors--;
|
|
}
|
|
|
|
return divisors;
|
|
} |