Can anyone help me with doing problem 12 on project euler? The question is asking which triangle number has more than 500 factors. The first few triangle numbers are: 1, 3, 6, 10, 15, 21, 28 ... Hope you understand the pattern, cause a can't explain it in words vary well.

Anyways I written the code in C, and it's just too slow. Here's an english version I wrote for easyness:

Generate the triangle number under (500^2)

loop until the triangle number's factors is more than 500
generate next triangle number

return triangle number

to find how many factors a number has:
divide number by prime number going from lowest to higher until it divides evenly
if the result is prime, tally the prime number and the result
if the result is not prime, tally the prime number and the result becomes the number and loop back to the "divide number by pr..." stage
add 1 and multiply everything in the tally that is not zero
the product is the number of factors

to generate prime numbers:
int n = 1, prime = 0
while prime is not prime
increase n if called on an odd time
loop back with prime = 6n-1 on every odd time and
loop back with prime = 6n+1 on every even time
return prime

and finally to check if a number is prime:
if number is under 2, its not prime
//this is a prime sieve
if number is 2, its prime
if number is divisible by 2, its not prime
if number is 3, its prime
if number is divisible by 3, its not prime
...
int count = what ever last sieve was
while count < sqrt number
if number mod count = 0
return 0 (not prime)
return 1 (is prime)

I'm going to attach the c version becouse its 341 lines long!

I think the time is being waisted mostly at the isprime step, or the countdiv (factoring) step.

Any suggestions to speed this puppy up? Thanks alot.

Hmm. Just had an idea (about 5 minutes after posting the above). Maybe the thing that slowing it down is the part where it reads the array. Look at function countdiv() I guess I could return the highest prime factor so it knows not to loop past it. Any other idea's?

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.

I actually don't understand the pattern. Enlighten me.

I actually don't understand the pattern. Enlighten me.

Err.. try understanding this (not tested):

int count = 1;
int triangle = 1;
while(1) {
printf("%d\n", triangle);
count++;
triangle += count;
}

You add 1 more than you did the last time starting a 1, 1+2, 3+3, 6+4... See I really can't explain it good:\$

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, ...

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;

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;
}

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.