3

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 my program is inefficient and oversized, but I just wanted to know why doesn't it work? Here's the code:

def check(z):

# checks if the given integer is prime

    for i in range(2, z):
        if z % i == 0:
            return False
            break
        i = i+1
    return True

def primegen(y):
# generates a list of prime integers in the given range

    tab = []
    while y >= 2:
        if check(y) == True:
            tab.append(y)
        i = i-1


def mainfuntion(x):
# main function; prints the largest prime factor of the given integer

    primegen(x)
    for i in range(len(tab)):
        if x % tab[i] == 0:
            print tab[i]
            break

mainfuntion(600851475143)

And here's the error:

for i in range(2, z):
OverflowError: range() result has too many items
user1843479
  • 51
  • 1
  • 3
  • 3
    You mixed `i` and `y` in `primegen`. As for the error, try `xrange`. – Lev Levitsky Nov 21 '12 at 22:57
  • 2
    It's bad practice to reference the variable `tab` inside `mainfunction` like you are doing. Your call to `primegen()` could return the list of primes, which you can assign to a variable: `primes = primegen(x)`, then the next line `for i in xrange(len(primes))`. – John Lyon Nov 21 '12 at 23:05
  • 1
    Welcome to Stackoverflow. I formatted your code for you, but please take a look at [this](http://stackoverflow.com/editing-help) and [this](http://meta.stackexchange.com/a/22189), and format code blocks properly next time. – BrtH Nov 21 '12 at 23:06
  • On another note, that's a terrifyingly inefficient method. O(n² / log n). – Daniel Fischer Nov 21 '12 at 23:18
  • related: [Stuck on Project Euler #3 in python](http://stackoverflow.com/questions/12999706/stuck-on-project-euler-3-in-python) – jfs Nov 22 '12 at 01:06

3 Answers3

11

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 :)

Community
  • 1
  • 1
RocketDonkey
  • 36,383
  • 7
  • 80
  • 84
  • 2
    You can replace range by xrange that does not store the whole list of elements in memory. – barracel Nov 21 '12 at 23:03
  • 1
    @barracel Indeed :) I am going to add an update in just a minute (in a meeting :) ) – RocketDonkey Nov 21 '12 at 23:05
  • 1
    Although `xrange` is "optimised" in the 2.x series so that implementations need only accept something that fits in a standard C `long` - @RocketDonkey not very busy in said meeting then? :) – Jon Clements Nov 21 '12 at 23:07
  • 1
    Even with `xrange`, 536870912 primes would be reached at 11891268401, the largest number this method would work for is then 11891268406 at an estimated running time of 20,000 years, give or take a factor of 3. – Daniel Fischer Nov 21 '12 at 23:42
  • @JonClements Ha, meetings - the best way to zap productivity at work but increase it on SO! – RocketDonkey Nov 22 '12 at 00:15
  • @user1843479 No problem - you're off to a good start, so have fun! – RocketDonkey Nov 22 '12 at 00:32
  • It is enough to avoid creating the list. The [simple division works](http://ideone.com/fbv5V4) in this case – jfs Nov 22 '12 at 01:11
  • @J.F.Sebastian Yeah, agreed - I guess I was aiming more to try to get him thinking about how to optimize the approach before coding anything. However I guess with how fast things process, that may be a moot point :) – RocketDonkey Nov 22 '12 at 01:15
1

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

seamonkey8
  • 17
  • 5
1

@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,2

while i*i <= n:      
    if n%i == 0:
        n //= i
    else: 
        i+=[1,2][i>2]
Stefan Gruenwald
  • 2,582
  • 24
  • 30