Posts Tagged ‘sage’

Problem 3 – Factoring

May 28, 2009

Problem 3 asks for the largest prime factor of a given integer. We could spend as much time as we wanted looking up factoring algorithms. I don’t really want to (I’d start at Numerical Recipes, since I already read those first few factoring algorithms). I noticed that sage has a factor command, so you can solve this problem in one line: print factor(whatever).

Well, not quite, because that prints out the whole factorization. For example, “print factor(18)” spits out “2 * 3^2”. We are only looking for the ‘3’.

Ok, so let’s split the string. There’s a handy function, called split, that you can use on any string to break it up into a list. If no argument is given, the string is split on spaces. If an argument is given, the string is split on that argument. So, for example

print "Hello  World".split()
print "Hello  World".split("or")

Will print out:

['Hello', 'World']
['Hello  W', 'ld']

Notice that the first line pulled out both spaces, and didn’t assume there was an empty string between them. If you want that behavior, you just need to do split(” “).

So, back to the problem. It might be tempting to try

print factor(18).split(" * ")[-1].split("^")[0]

to split the factorization into a list, grab the last term (presumably the largest), then split that on “^” (in case it’s a power, like for factor(18)), and just take the base of exponentiation. That’d be pretty sweet.

The problem, as you might have guessed by now, is that factor(18) doesn’t return a string object (though, you could use str() to convert it to a string, and then the line above would work). It only looks that way, when we print it. What really gets returned? According to the documentation, we get a Factorization object out. Looking at that documentation, we can index factors of a Factorization exactly like it were a list of tuples (base, power). So factor(whatever)[-1][0] will solve problem 3 (assuming the [-1] index actually does pull out the biggest base, which I think is the case (there’s a sort method on Factorization objects, if not)).

If you get tired of the ring of integers, there will be Factorization objects waiting for you when you move to another ring.