-
Notifications
You must be signed in to change notification settings - Fork 0
/
euler012.c
98 lines (86 loc) · 1.67 KB
/
euler012.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/* https://projecteuler.net/problem=12
* 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?
*
* David Timm 2014-09-16
*/
#include <stdio.h>
#include <math.h>
int count_factors(int);
int next_prime(int);
int main(void)
{
int current = 1;
int triangle = current;
while(1)
{
if(count_factors(triangle) > 500) break;
triangle += ++current;
}
printf("%d: %d\n", triangle, count_factors(triangle));
return 0;
}
int count_factors(int number)
{
int factors = 1;
int i = 0;
int current = number;
int prime = 2;
while(current > 1)
{
if(current % prime == 0)
{
i++;
current = current / prime;
}
else
{
prime = next_prime(prime);
factors = factors * (i+1);
i = 0;
}
}
factors = factors * (i+1);
return factors;
}
int next_prime(int current)
{
if(current==2) return 3;
int i;
int next = current + 2;
int is_prime = 0;
int failed = 0;
double root = sqrt(next);
while(!is_prime)
{
for(i=3;i<root;i++)
{
if(next%i == 0)
{
next += 2;
failed = 1;
break;
}
}
if(failed == 0) is_prime = 1;
failed = 0;
}
return next;
}