I'm a professional game developer from Wakefield, England, working as a senior programmer for Rebellion North.

I'm a married father of five and I a also sometimes do Retroburn stuff.

Martin 'Bytrix' Caine

Father. C++ Games Programmer. Cyclist. Guitarist.

Tags

2013 3d alphalabs amazon apple archivirtual asynchronous battlefield bad company 2 ben 10 bepu beta blackmagic design blog blue marble bootcamp borderlands bsp calibration charity charvel childsplay comments competition content tracker counter-strike crash csgo css3 cycling dear esther deferred deus ex develop conference direct x discipline documentation doom 3 bfg dpi dr bott eidos elite force email deliverability eurogamer expo facebook focus fresnel game development game horizon game republic gamedev games gaming geoip girls make games global offensive grid guitar half-life 2 hawken hd7 hobbyist htc humble indie bundle imac indie indie trials indietrials intensity pro ip-countryside iron man 3 jamulus rift jquery kids kinect launch conference left 4 dead live lost mac mac osx manchester manhacks mass effect 2 matrox maya minecraft mirrors edge montreal morrowind movies museum of the microstar music mxo2 mini mysql nausea network networking nokia normal mapping obj oculus rift omnitrix ouya pedal for pounds php physics playstation suite port25 portal portal 2 positron posters powermta project aedra project euler promotion properties proton pulse ps vita ps4 psn racer reddit rendering retroburn game studios reviews rift racer riftracer roadkill roller coaster sdl2 shadow racers sharks shoct skyrifters snds space cadet spam trap star trek steam stencyl storage super stock sd1 fr superhot team fortress 2 tesselating tesselation texture editor thunderbird thunderclap ticktock games tiga track builder track bulder trials tv twitter uk ultimatrix usergroup vequencer video vireio visual assist visual studio vorpx voucher vr vr cinema war thunder warren web willow windows 8 windows 8.1 windows phone 7 workbench wp7 wp7dev xbla xblig xblig network xbox xbox live indie games xna xnaukug xperia play zombies on the holodeck

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 then
for( $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 first
rsort( $factors );

// loop through factors
foreach( $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';

?>

If you found this post helpful please leave a comment below:

Comments

Tags: php project euler web