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';?> ```     