I'm a professional game developer from Wakefield, England, working for TickTock Games.
I'm a married father of five and I am also the director and lead programmer of Retroburn Ltd.
Martin 'Bytrix' Caine
Father. C++ Games Programmer. Cyclist. Guitarist.
Monday, May 31st 2010 / Web

# Project Euler - problem 3

The third problem from Project Euler was a little more complex:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143

I split this in to two processes. First I calculated the factors of 600851475143, I then ordered them in reverse order.

I then tested each factor to see if it was prime by incrementing from 2 to the value of the factor while testing the division by the variable. If a division resulted in a whole number then the factor is not prime and we move onto the next factor.

I'm sure there are more efficient ways to determine whether a value is prime (simple only testing division by primes would be an option).

The program returns when we find a prime number among the factors:

``` <?/*******************************************************************  ProjectEuler.net  *  Problem 3  *  2010-05-31  *  Martin Caine *******************************************************************///The prime factors of 13195 are 5, 7, 13 and 29.//What is the largest prime factor of the number 600851475143 ?\$total = 0;// create an array to store the factors of 600851475143\$factors = array();// we won't ever hit 600851475143 as we'll break well before thenfor( \$i = 2; \$i<600851475143; \$i++ ){    // check to see if dividing by this returns a whole number    \$result = 600851475143/\$i;    if( \$result == (int)\$result )    {        // if this is in our array we have found all the factors        if( in_array( \$i, \$factors ) )        {            break;        }        \$factors[] = \$result;        \$factors[] = \$i;    }}// sort factors with largest firstrsort( \$factors );// loop through factorsforeach( \$factors as \$factor ){    // by default, assume prime, we mark as not being prime in the loop    \$isPrime = true;    for( \$i=2; \$i<\$factor; \$i++ )    {        \$result = \$factor/\$i;        if( \$result == (int)\$result )        {            // we found a factor so it's not prime            \$isPrime = false;            break;        }    }        if( \$isPrime )    {        // we found our prime, and we're testing largest first so output and die      echo \$factor;        die();    }}echo 'no prime factor found';?> ```     