Duncan's blog

September 21, 2014

Project Euler: problem 3 (PHP) – Largest prime factor

Filed under: PHP,Project Euler — duncan @ 8:00 am

3I previously blogged about this Project Euler puzzle 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and I’d appreciate any feedback on my PHP code.

Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

Ok, now we’re starting to get into some more interesting code. I’m merely trying to convert my previous CFML approach into PHP, and assuming the basic logic is correct. There’s probably much better ways to do this though.  I did simplify my code somewhat this time, previously I was using recursion to calculate all the factors.  It’s still not ideal (I’m aware of an obvious flaw in it), but it returns me the correct answer.

<?php
$limit = 600851475143;
$primes  = array();

function isPrime($x)
{
	if ($x < 2)
	{
		return false;
	}
	
	if (($x % 2 == 0) && ($x > 2))
	{	// a multiple of 2, but not 2 itself
		return false;
	}
	
	for ($i = 3; $i <= sqrt($x); $i += 2)
	{
		if ($x % $i == 0)
		{	// found a factor of x
			return false;
		}
	}
	
	return true;
}

function findPrimes($x)
{
	// need to re-declare $primes as a global variable so this function can access it:
	global $primes;
	
	for ($i = 3; $i < sqrt($x); $i += 2)
	{
		if ((fmod($x,$i) == 0) && isPrime($i))
		{
			if (! in_array($i, $primes))
			{
				array_push($primes, $i);
			}
		}
	}
}

findPrimes($limit);
rsort($primes,  SORT_NUMERIC);
echo $primes[0];

So some things worth mentioning.

1. In order to access the variable $primes inside the findPrimes function, I had to re-declare it as ‘global’ within that function. I should just have rewritten the function to simply return an array.

2. I couldn’t simply do $x % $i == 0 to calculate the modulus, this didn’t seem to work due to the size of the values. I didn’t bother spending any time to investigate at what point this stopped working, what size of integers PHP couldn’t happily handle, or what was the exact problem. Instead I just used the fmod() function, which seemed fine.

3. Rather than just dump out the entire array, I used rsort() to sort it numerically in descending order, then output the first element in the array.  There’s better ways obviously of getting the last element in an array.

4. I’m using the array functions in_array($value, $array) and array_push($array, $value) – notice already the inconsistency in the order of the arguments, something I’ve seen mentioned in a few places.  These are the PHP equivalents of CFML’s ArrayFind(array, value) and ArrayAppend(array, value)

Advertisements

4 Comments »

  1. […] re-using my isPrime function from the third problem, included in its own file, then simply loop over every odd number greater than […]

    Pingback by Project Euler: problem 10 (PHP) | Duncan's blog — September 28, 2014 @ 8:02 am | Reply

  2. […] Re-using my isPrime function from Problem 3. […]

    Pingback by Project Euler: problem 49 (PHP) – Prime permutations | Duncan's blog — October 16, 2014 @ 8:01 am | Reply

  3. […] Re-using the isPrime function from Problem 3. […]

    Pingback by Project Euler problem 58 (PHP) – Spiral primes | Duncan's blog — October 21, 2014 @ 8:02 am | Reply

  4. […] Re-using my isPrime function from puzzle 3. […]

    Pingback by Project Euler: problem 35 (PHP) – Circular primes | Duncan's blog — October 22, 2014 @ 8:01 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: