Euler Project #3 In Python

I'm trying to solve the Project Euler problem 3 in Python: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? I know m

Solution 1:

The reason is that a list in Python is limited to 536,870,912 elements (see How Big can a Python Array Get?) and when you create the range in your example, the number of elements exceeds that number, causing the error.

The fun of Project Euler is figuring out the stuff on your own (which I know you're doing :) ), so I will give one very small hint that will bypass that error. Think about what a factor of a number is - you know that it is impossible for 600851475142 to be a factor of 600851475143. Therefore you wouldn't have to check all the way up to that number. Following that logic, is there a way you can significantly reduce the range that you check? If you do a bit of research into the properties of prime factors, you may find something interesting :)

Solution 2:

First, in the first code block, do not use i = i+1 since the for loop takes care of it. Secondly, use xrange to make a generator instead of a list.

Solution 3:

This is the code that I used!!

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print n

-M1K3

Solution 4:

@seamonkey8: Your code can be improved. You can increase it by 2 rather than one. It makes a speed difference for really high numbers:

n,i = 6008514751231312143,2while i*i <= n:      
    if n%i == 0:
        n //= ielse: 
        i+=[1,2][i>2]