Wednesday, January 19, 2011

Problem 3 -The Largest Prime Factor of a Composite Number

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

This one had me stumped for a while but mostly because of some type-casting issues with Supercolllider. sclang comes with an Integer.factors method that works great for 32-bit integers, up to a point.
So while

correctly returns
[5, 7, 13, 29]

If you ask

it curiously returns
[ 2147483647 ]

which is probably not coincidentally the Mersenne Prime (2**31)-1 and probably has something to do with sclang overflowing the bit register for a 32-bit integer.

So after a few hrs of fighting w/ sclangs weird type-casting issues I came up with the following recursive function:

//function to find distinct factors of num, not complete factorization
//factors is an empty Array that we can add to

~f = {|num, f=2,factors=([])|
break if we've already gotten to the square root of num
the final value of num is the last factor
because it was the last even divisor of num/f

~f.(num/f, f+1,factors.add(f));
~f.(num, f+1,factors);

//number in question has to be cast as a Float for 64-bit precision

It's pretty fast, though not tail-recursive (and the 2 function calls seems like bad form. There's probably also a better way to do recursive functions than with the pseduo-global ~variable stuff). It doesn't do a complete factorization, just finds the unique factors of the number. The trick to gaining speed is that once you find a factor of composite num, you divide by the factor so that the number that you continue to factor is a little smaller, and even if you're just testing every integer sequentially for divisibility, your factor catches up with num pretty quickly. It probably helps that in this case, the test number has no repeating factors and most of the factors are pretty large.

No comments:

Post a Comment