Duncan's blog

October 21, 2008

Project Euler: problem 3

Problem 1 took a couple of minutes, Problem 2 not much longer than that. Problem 3 took me several hours over a few days to work out! Hopefully some of the work I’ve done will stand me in stead for future problems involving prime numbers.

Problem 3:

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

What is the largest prime factor of the number 600851475143 ?

Initially I thought to use a Sieve of Eratosthenes to find all the primes less than 600851475143 (the limit). Then check which of those primes were its factors. This worked fine for 13195, but timed out on the larger number.

Then I tried doing the opposite: finding all the factors of the limit, then checking which of them are prime. Again, it timed out on the big number.

Then I read somewhere that all primes, except 2 and 3, are either +1 or -1 from a multiple of 6. e.g. 97 is prime. 97-1 = 96, which is 6 x 16. So I tried using that to test for things that might be prime, before applying the more time consuming check to see if it actually was prime. Again, no dice.

It’s worth mentioning that I’m doing this on an old CF 5 server. Some of my earlier attempts might have ran ok on CFMX. Also I’d have had the option to slip into Java, perhaps for casting the limit to a long int. And I’d be able to use the CFFunction tag rather than embed functions into CFScript.

After reading up a bit more, I learned that all I had to do was find the first prime factor, then divide the limit by that, and find the prime factor of whatever that is, and so on. Doing this you shouldn’t need to go any higher than the square root of your number each time.

So for instance, using 13195 as our limit:

  • loop through 13195 until find the first prime factor
  • it’s 5. store that in an array
  • divide 13195 by 5 = 2639
    • loop through 2639 until find the first prime factor
    • it’s 7. add that to our array
    • divide 2639 by 7 = 377
      • loop through 377 until find the first prime factor
      • it’s 13. add that to our array
      • divide 377 by 13 = 29.
        • 29’s larger than the square root of 377, so we’ll stop there
    • the next prime factor of 2639 is 29 (coincidentally). add that to our array
    • divide 2639 by 29 = 91
    • 91’s larger than the square root of 2639, so we’ll stop there
  • there are no more prime factors of 13195

So, the best way to tackle this is with a recursive function. Always fun to get your head around. Rather than try and pass an array of primes as a parameter to the function, I simply set the array in the variables scope, and continually appended to it. Not how I’d normally do it (but then I don’t normally use recursion if I can help it), but I saw an article on recursion in coldfusion which did something similar, using the variables scope.

I wrote my own IsPrime function, and I had to use the ProperMod UDF from CFLib. The reason for this is that Coldfusion can only handle 32-bit ints, i.e. between -2,147,483,648 and 2,147,483,647. Anything outwith that I think it converts to a string. The MOD statement expects an int, not a string, so it throws an error. In some cases you can still use this value for doing mathematical functions on, e.g. I had no problem finding a square root, even though the Sqr() function also expects an integer. If I was using CFMX, I could probably have used Java to cast to a long integer.

All primes except 2 are odd, so when looping we can go in steps of 2 rather than the normal 1. I sort of deal with this a bit cack-handed, and for the parent loop, it does it in steps of 1. Perhaps if I used a while loop instead of a for loop, I could have got this code better.

Here’s the code. It’s far from optimal, but it works!

<cfset limit = 600851475143>
<cfset primes = ArrayNew(1)>

<cfscript>
function isPrime(x)
{
	var isPrime = true;
	var i = 0; 
	
	if (x LT 2)
	{
		return false;
	}
	
	if ((NOT ProperMod(x, 2)) AND (x GT 2))
	{	// a multiple of 2, but not 2 itself
		return false;
	}
	
	for (i = 3; i LTE SQR(x); i = i + 2)
	{
		if (NOT ProperMod(x, i))
		{	// found a factor of x
			return false;
		}
	}
	
	return isPrime;
}

/**
* Computes the mathematical function Mod(y,x).
*
* @param y      Number to be modded.
* @param x      Devisor.
* @return Returns a numeric value.
* @author Tom Nunamaker (tom@toshop.com)
* @version 1, February 24, 2002
*/
function ProperMod(y,x) {
	var modvalue = y - x * int(y/x);
	
	if (modvalue LT 0) modvalue = modvalue + x;
	
	Return ( modvalue );
}

function findPrimes(x,y)
{
	/*Find the first prime factor of limit.  
	Divide the limit by that factor.  
	Recursively, find the first prime factor of that number 
	(not including the previous number we already found).  etc. 
	These are all the prime factors of limit.  */
	// x = limit
	// y = where to start from
	var i = 0; 
	var j = 0; 
	var step = 2;
	
	if (y EQ 2)
		step = 1;
		
	for (i = y; i LT SQR(x); i = i + step)
	{
		if ((NOT ProperMod(x, i)) AND IsPrime(i))
		{	// i is a factor of x, and it's prime
			if (NOT ListFind(ArrayToList(variables.primes), i))
			{	// it's not already in our array of primes
				ArrayAppend(variables.primes, i);
				j = x / i;
				if (i+1 GT SQR(j))
				{	// is there any point carrying on?
					if (i GT 2)
						findPrimes(j, i+2);
					else
						findPrimes(j, i+1);
				}
			}
		}
	}
}
</cfscript>

<cfset findPrimes(limit, 2)>
<cfdump var="#primes#">
Advertisements

5 Comments »

  1. […] numbers again, good job I spent so long trying various things out on problem 3. I just copied the IsPrime function I did then (except removed the custom Mod function and just […]

    Pingback by Project Euler: problem 7 « Duncan’s blog — October 25, 2008 @ 7:30 am | Reply

  2. […] spiral. For each value, work out if it is prime (re-using the IsPrime function I first used back in problem 3). Keep count of how many primes there are. Also keep track of how long the side of our spiral is. […]

    Pingback by Project Euler problem 58 « Duncan’s blog — December 19, 2009 @ 11:00 am | Reply

  3. “Doing this you shouldn’t need to go any higher than the square root of your number each time.”

    I noticed in your example how you go about find the 1st prime factor, adding to array, etc., that each quotient is higher than the square root of each limit (13195, 2639, etc.) you came up with.

    I know, however, that this was posted way back in 2008 so I’m not sure if you are still active.

    Comment by LaserWraith — March 16, 2010 @ 8:59 pm | Reply

  4. Wow, didn’t know there was a CF code and it’s way too verbose that what you can do with 12 LOC in Scala using Functional Programming..

    Comment by James — August 24, 2012 @ 4:57 pm | Reply

  5. […] 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 […]

    Pingback by Project Euler: problem 3 (PHP) | Duncan's blog — September 21, 2014 @ 8:11 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

Blog at WordPress.com.

%d bloggers like this: