Still room for inprovement, but I got it working a reasonalble speed.. I think I kinda solved this thread on my own, but if there are any other suggestion's, I'm still interested in making my code faster.
The first improvement I found was that you don't need to regenerate all the primes every time. Split the array into separate arrays. One global array of primes and one for factor counts.
This improved from ??? to 10 mins or so.
I don't know how long it originally took, I killed it after a while.
To make it work change the fillprimes function to just fill the next x primes ...
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);
}
You see I changed the test to maxPrime and test the prime value instead of the count.
Now everywhere you loop over the array(s) you only loop until maxPrime is reached.
Next is findprimefactor. You call tally which iterated through the entire array again. Now as you are iterating over the prime array you have the index of the factor to increment.
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;
{
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;
}
When it checks the result of the division it could just continue as if it isn't prime. That would be the same as the search done in isprime. But a quick binary search across the existing primes works even better.
The binary search code came outta my head so it probably has holes. But it worked for the few values I tested.
Now the time was reduced to around 5 mins.
I tweaked a few standard things without much speed up.
Then the biggie ... to get the factors to come out right you have to gen primes all the way up to 'number'. But for most things you only need primes up to sqrt(number) +1.
The only time you really need all is if number is prime. Hmmm... all primes only have to factors. No need to factor or count primes at all!
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;
}
Boom! It takes less than a second to calculate the first 500 term triangle.
I've attached the changed file.
Offline 
Marked 
