The attachment preview is chopped off after the first 10 KB. Please download the entire file.

```
/* Euler 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?
*/
#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <time.h>
/* global */
#define MAX_PRIMES 76576500 //20000 //11765 76576500
int *primes = 0;
int *primefactor = 0;
int primeCount = 0;
/* defs */
int trianglediv(int nofdiv);
int triunder(int max, int *count);
int countdiv(int number);
void findprimefactor(int number, int *output);
void fillprime(int maxPrime);
int nextprime(int *n, int *c);
int isprime(int number);
void tally(int *output, int n);
void init(int size, int *array);
/* main */
int main() {
int cnt = 500;
primes = (int *) malloc( sizeof(int)*MAX_PRIMES);
primefactor = (int *) malloc( sizeof(int)*MAX_PRIMES);
printf("\nThe first triangle number to have at least %d divisors is: %d\n",
cnt,trianglediv(cnt));
free(primes);
free(primefactor);
getchar();
return 0;
}
int trianglediv(int nofdiv) {
/* This function returns first triangle number to have over 'nofdiv' divisors.
It works by generating triangle numbers until it finds one with over
'nofdiv'. We can start generating the triangle numbers at the triangle number
under 'nofdiv'^2. */
int hrs = 0;
int mins = 0;
int secs = 0;
int n = 0;
int terms = 0;
int maxTerms = 0;
int tics;
int count = 1;
/* Fast forward to a number which can possible hold nofdiv factors. */
int triangle = 1; //triunder((int) pow(nofdiv, 2), &count);
count++;
/* Make a variable length array. The
second dimention holds prime numbers,
and the fist dimention holds how many
of that prime number there is. */
while((terms = countdiv(triangle)) < nofdiv) { /* while there arent enough divisors */
n++;
if( terms >maxTerms )
{
maxTerms = terms;
tics = clock()/1000;
hrs = tics/3600;
tics -= hrs * 3600;
mins = (tics/60);
tics -= mins * 60;
secs = tics;
printf("\n%02d:%02d:%02d - %8d tested (max terms %5d for %9d) primes %8d\n",hrs,mins,secs, n, maxTerms, triangle,primeCount);
}
else if( (n&0xF) == 0)
{
printf(".");
}
triangle += count; /* Get next triangle number */
count++;
}
n++;
maxTerms = terms;
tics = clock()/1000;
hrs = tics/3600;
tics -= hrs * 3600;
mins = (tics/60);
tics -= mins * 60;
secs = tics;
printf("\nDONE!\n%02d:%02d:%02d - %8d tested (max terms %5d for %9d) primes %8d\n",hrs,mins,secs, n, maxTerms, triangle,primeCount);
// printf("Final %d -> %d\n", triangle, terms);
return triangle;
}
int triunder(int max, int *count) {
/* This function returns the next triangle number after 'max'. It also sets 'count'
to where it needs to be to generate futher triangle numbers. */
int nexttri = 0; /* Hold's next possible triangle number */
do {
nexttri += *count; /* Generate the next triangle number */
(*count)++;
}while(nexttri < max);
return nexttri;
}
int countdiv( int number) {
/* This function returns the number of divisors. It finds the prime divisors,
adds 1 to each, and finds the product of all of them. It returns the product.
*/
int count = 0;
int product = 1;
int maxPrime;
if(isprime(number) )
{
return 2;
}
maxPrime = (int) sqrt(number)+1;
fillprime(maxPrime); /* generate next x primes */
init(primeCount, primefactor); /* clear count array array with 0's */
findprimefactor(number, primefactor); /* count each prime factor */
while(primes[count] <= maxPrime) {
if(primefactor[count] != 0) /* If there is a number of that prime */
product *= (primefactor[count]+1); /* add 1 and multiply */
count++;
}
return product;
}
int findPrime1(int p)
{
int n = 0;
while(primes[n] < p)
{
n++;
}
if(primes[n] == p)
return n;
return -1;
}
int findPrime(int p)
{
int n = primeCount>>1;
int d = n>>1;
while(d)
{
if(primes[n] < p)
{
n = n + (d);
}
else if(primes[n] > p)
{
n = n - (d);
}
else
return n;
d>>= 1;
}
return -1;
}
void findprimefactor(int number, int *output) {
/* This function will find all of the prime factors. It works by dividing number
by primes until it evenly divides. That prime is a prime factor, and if the
result is also prime, its is a prime factor. If the result is not a prime
factor, it becomes the new 'number'. */
int n = 0;
int p = 0;
int n1 = 0;
while(n<primeCount)
{
p = primes[n];
if(number == p) { /* if result is 1 */
output[n]++; /* Add that 'number' to its place on first dim */
return;
}
if( (number % p) ==0) { /* number evenly divides into p */
output[n]++; /* Add that 'p' to its place on first dim */
number /= p;
n1 = findPrime(number);
if(n1 != -1) { /* if result is prime */
output[n1]++; /* Add result to its place on first dim */
return;
}
/* if result is not prime */
/* The result is the new number */
n = 0;
}
else
n++;
}
// should not get here except on 1
if(number>0)
{
printf("\nRemainder - %d",number);
}
return;
}
void fillprime( int maxPrime ) {
/* This function fills the second dimention of an array with primes. It uses the
modified version of problem 2 attemp 2's 'nextprime' and 'isprime' used in
problem 7. Why do all these's questions rely on prime numbers? */
static int c = 0, n = 0;
do {
primes[primeCount] = nextprime(&n, &c);
}while(primes[primeCount++] <= maxPrime);
}
int nextprime(int *n, int *c) {
/* This function will return the next prime number. Simply set n and c at 0 and
call the function whenever you need the next prime number. This is bassed off
of the one in problem 3, except will work for more than 12 calls. I thought
that 6n-1 and 6n+1 would work for all n's, but aparently not. So I just put
an isprime() to trap it. */
int prime = 0;
do {
if(*n == 0 && *c == 0) { /* First call, return 2 */
(*c)++;
prime = 2;
}
else if(*n == 0 && *c == 1) { /* Second call, return 3 */
(*c)--;
(*n)++;
prime = 3;
}
else if(*c == 0) { /* Even call, return 6*n-1 */
(*c)++;
prime = (6*(*n))-1;
}
else if(*c == 1) { /* Odd call, return 6*n+1 */
(*c)--;
prime = (6*((*n)++))+1;
}
}while(!isprime(prime));
return prime;
}
int isprime1(int number) {
int maxCnt = (int)sqrt(number) + 2;
int count = 0;
if(number < 25)
return 1;
while (primes[count] < maxCnt) {
if (number % primes[count] == 0) /* % means modulo, basicly just the remainder. */
return 0;
count ++; /* Count = next prime number */
}
return 1;
}
int isprime(int number) {
/* This function will return 1 if number is prime. It works by dividing 'number'
by every possible number it could divide evenly into. If it dosent divide
into anything upto its square root, the number wont divide into anything.
Also dont check even numbers. If its divisible by 2, it would be divisible by
all even numbers. In problem 12 I added a sieve. Basicly, if the number is
divisible by a prime number, its not prime. */
int max = (int)sqrt(number) + 2;
int count = 79; // 23; /* Start at 23 so we can increase by 2 for odd numbers. */
if (number <= 1) /* if the number is 1 or under, its not prime */
return 0;
if (number == 2) /* if the number is 2, its prime */
return 1;
if (number % 2 == 0) /* if the number is divisible by 2 its not prime. */
return 0;
/* Extra sieve starts here */
if(number % 3 == 0) {
if(number == 3)
return 1;
return 0;
}
if(number % 5 == 0) {
if(number == 5)
return 1;
return 0;
}
if(number % 7 == 0) {
if(number == 7)
return 1;
return 0;
}
if(number % 11 == 0) {
if(number == 11)
return 1;
return 0;
}
if(number % 13 == 0) {
if(number == 13)
return 1;
return 0;
}
if(number % 17 == 0) {
if(number == 17)
return 1;
return 0;
}
if(number % 19 == 0) {
if(number == 19)
return 1;
return 0;
}
if(number % 23 == 0) {
if(number == 23)
return 1;
return 0;
}
if(number % 29 == 0) {
if(number == 29)
return 1;
return 0;
}
if(number % 31 == 0) {
if(number == 31)
return 1;
return 0;
}
if(number % 37 == 0) {
if(number == 37)
return 1;
return 0;
}
if(number % 41 == 0) {
if(number == 41)
return 1;
return 0;
}
if(number % 43 == 0) {
```