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#">
