Euler Project #3 in Python

Question

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

You mixed i and y in primegen. As for the error, try xrange. — Lev Levitsky
– Lev Levitsky, Commented Nov 21, 2012 at 22:57
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
– John Lyon, Commented Nov 21, 2012 at 23:05
Welcome to Stackoverflow. I formatted your code for you, but please take a look at this and this, and format code blocks properly next time. — BrtH
– BrtH, Commented Nov 21, 2012 at 23:06
On another note, that's a terrifyingly inefficient method. O(n² / log n). — Daniel Fischer
– Daniel Fischer, Commented Nov 21, 2012 at 23:18

Community · Accepted Answer · 2017-05-23 12:23:31Z

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

edited May 23, 2017 at 12:23

CommunityBot

11 silver badge

answered Nov 21, 2012 at 22:56

RocketDonkey

37.4k8 gold badges83 silver badges84 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

barracel Over a year ago

You can replace range by xrange that does not store the whole list of elements in memory.

RocketDonkey Over a year ago

@barracel Indeed :) I am going to add an update in just a minute (in a meeting :) )

Jon Clements Over a year ago

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

Daniel Fischer Over a year ago

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.

RocketDonkey Over a year ago

@JonClements Ha, meetings - the best way to zap productivity at work but increase it on SO!

|

seamonkey8 · Accepted Answer · 2013-03-02 02:59:46Z

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

answered Mar 2, 2013 at 2:59

seamonkey8

175 bronze badges

Comments

Stefan Gruenwald · Accepted Answer · 2020-12-28 20:02:50Z

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]

edited Dec 28, 2020 at 20:02

answered Dec 13, 2014 at 16:47

Stefan Gruenwald

2,63827 silver badges31 bronze badges

Collectives™ on Stack Overflow

Euler Project #3 in Python

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

8 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related