06.02.08
Project Euler: Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
A solution:
We can use the factorize function written for Problem 5, but it needs to be modified. The number to be factored is so large that the upper limit of numbers that need to be checked as factors is of type long, rather than of type int. The range() function doesn’t like numbers that large (unsurprisingly, as that would be a very very very long list to store), so a while loop needs to be used instead of a for loop.
def factorize(num):
powers = []
limit = (num/2)+1
i = 2
while i <= limit:
while num % i == 0: # ie, i is a factor of num
powers.append(i)
num = num/i
i += 1
if num == 1: break # ie, all factors have been found
if len(powers) == 0: powers.append(num) # num is prime
return powers
This function can then be used to find the prime factors of the given number.
There are ways this method can be improved: if the factor 2 is handled separately before the while loop, then the loop only needs to be done for odd numbers, using half of the iterations. As well, a separate function that tests for primality could be called at the beginning: since a prime test only needs to check up to sqrt(number) instead of number/2, it can be a lot faster to know if the number itself is prime, rather than trying to find all of its factors.
parseidon said,
5 June, 2008 at 7:16 pm
Hi, me again. I must say I cheated a bit by looking at theory from people who had to solve similar problems. I just don’t have the level of maths to know this at the base (which is why I do the project), so I managed to pull this:
import math
def getFactor (n):
…i = int(math.sqrt(n))
……while n%i!=0:
………i-=1
……return i
def largestPrimeFactor (n):
…a = n / getFactor(n)
…return getFactor(n / getFactor(a))
print largestPrimeFactor(600851475143)
It’s really fast, and although I didn’t understand all the explanations from whatever site, fiddling around with numbers (based on their example) let me solve it. To be honest, I’m still not 100% sure of what the relation between all the numbers are, but I think I grasp most of it.
I guess the only real way I have to understand problems is to get to the roots of how they managed to get the example. If they didn’t give an example, I wouldn’t even have more than 2-3 completed, I think.
redochre said,
5 June, 2008 at 9:13 pm
Okay, if you take 600851475143 (factors are [71, 839, 1471, 6857]) and multiply it by a bigger prime — say, 7589 — and use your method, it doesn’t work. The answer that it gives isn’t even prime. I kind of understand what the algorithm is getting at, though it’s going about it in a very confusing way (myself and my boy have five math degrees between us and we just spent half an hour trying to work it out).
One problem with the algorithm is that it’s not recursive. You call the getFactor() three times, but I think three is just a magic number in this case because you have four factors. Or something. Something about that just isn’t right.
I’m not sure that an algorithm for specifically finding the biggest prime factor of a number is going to be, in general, faster than just prime factoring the number and picking the biggest of the factors.
I’ll try write a better prime factoring algorithm tomorrow that incorporates some of the ideas from what you’ve written, as I understand them.
parseidon said,
5 June, 2008 at 9:58 pm
Well, I’m sorry. Somehow it worked with both cases and 2-3 others I tried. I just assumed it was alright on most cases. I’ll go back and find something that works for real then. Thanks for pointing the flaw out.
redochre said,
6 June, 2008 at 5:20 am
No need to apologize! I’ve had that happen a couple of times to me in these euler problems: that I get the solution and then, looking back later, realizing that my algorithm shouldn’t actually have worked. It’s a strange and frustrating thing.
parseidon said,
6 June, 2008 at 11:17 am
Just revised your code, and the kind of recursion I was somehow attempting with n/factor whatever was the one with
while num % i == 0:
…num/=i
Which was the missing part of getFactor except I just couldn’t wrap my head around it for some reason (come on, I’ve done recursions way harder than this one :( )
So thanks for the solution.
redochre said,
6 June, 2008 at 12:38 pm
You’re welcome, I hope things are making more sense!
Kranny said,
9 January, 2009 at 7:43 am
My code goes like this:
import math
def isprime(n):
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return 0
return 1
l=[]
for x in range(2, math.sqrt(600851475143)):
if(isprime(x)):
if(600851475143 % x == 0):
print x
x=x+1
Though i dont get a correct answer..