Python Project Euler 3

Question

I'm new to python, I'm trying to help my girlfriend learn coding through project Euler, I suggested she start with python. Unfortunately on problem 3 we came to a strange error.

For finding the prime factors of smaller numbers, this seems to work fine, but trying to find the prime factors of 600851475143 it just chokes.

I was under the impression python was extremely forgiving for maximum integer values, so I don't know why it doesn't work here.

def is_prime (n) :
    for i in range (2, n) :
        if n % i == 0:
            return 0
    return 1 

n = 600851475143

for i in range (1, n) :
    if n % i == 0 :
        if is_prime (i) == 1 :
            print i

If anyone could lead me right, I'd be very thankful!

David

edit: I'm well aware how sub-optimal this all is!

Python is working but 600 billions of not simple iterations are going to take "forever". — Eric Levieil, Apr 14 '15 at 16:13
I'm fairly sure this is not the case, if I put in print i before checking if n % i == 0, nothing is outputted still. — Plastonick, Apr 14 '15 at 16:14
Python chokes on trying to allocate a huge list for `range(2, 600851475143)`. Switch to `xrange` and then continue debugging. — user4815162342, Apr 14 '15 at 16:16
For what it's worth, Project Euler problems are not really designed for introduction to programming concepts. They are rather an exercise in devising clever algorithms where brute force attempts would fail, as they did here. — Cory Kramer, Apr 14 '15 at 16:17
Have you tried using xrange in place of range? See [here](http://stackoverflow.com/questions/135041/should-you-always-favor-xrange-over-range). — Jon Bloom, Apr 14 '15 at 16:17
Two comments: I disagree with Cyber and think PE is a great way to learn programming. It really focuses on the most basic computational ideas. Second--and maybe you already know this--your upper bound could be much lower. — jds, Apr 14 '15 at 16:20
thank you user4815162342 and Jon Bloom, that seems to have fixed it! And Cyber2, yes, my girlfriend is not fond of the maths, but they are nice set interesting exercises to give learning a goal of sorts. I'll have a look soon if there is a similar goal-orientated learning method more suitable, thank you! — Plastonick, Apr 14 '15 at 16:21
Thank you gwg, yes I know the upper bound should be √n in is_prime, and (without conditionals and assuming n may be prime) n+1 in the second for loop. My girlfriend is somewhat maths-phobic though, so I try to keep explanations to an absolute minimal! — Plastonick, Apr 14 '15 at 16:27
@Plastonick Perhaps you could try the Sieve of Eratosthenes method? It's a lot more efficient by not evaluating numbers the algorithm knows aren't prime. I would post this as an answer but there isn't much to elaborate from this SO question: http://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python — matrixanomaly, Apr 14 '15 at 16:36
@Plastonick, I like project euler for picking up a new language as it gives some problems to work through, but its not the best for learning to program in the first place. You might want to checkout http://www.codecademy.com/ and/or http://www.codewars.com/. — Matt, Apr 22 '15 at 16:32

score 3 · Accepted Answer · answered Apr 22 '15 at 16:19

3

Since no one answered the obvious, use xrange instead of range:

def is_prime (n) :
    for i in xrange (2, n) :
        if n % i == 0:
            return 0
    return 1 

n = 600851475143

for i in xrange (1, n) :
    if n % i == 0 :
        if is_prime (i) == 1 :
            print i

But keep in mind this is still very slow, but you won't run into MemoryErrors.

answered Apr 22 '15 at 16:19

Juan Lopes

10,143
2
25
44

Thank you, yes this is exactly what I was looking for. Optimality will come afterwards I think! – Plastonick Apr 23 '15 at 17:01

score 1 · Answer 2 · answered Apr 14 '15 at 16:22

1

see this algorithm to go through numbers by dividing on factors, it's more efficient:

while num > 1:
    if num % div == 0:
        num /= div
        div -= 1
    div += 1

answered Apr 14 '15 at 16:22

Julia K

46
7

Thank you, but I was just wondering why it didn't work, it seems range was the issue and substituting it with xrange has fixed it. – Plastonick Apr 14 '15 at 16:25

Antoni Gual Via · Answer 3 · 2015-04-22T16:13:42.303

Finding the prime factors of big numbers is not a trivial thing. Criptography is based in keys that are the product of two keys big enough so that event the biggest parallel computers choke on them. When there is an improvement on computing power or methods you just use bigger nimbers to keep it safe,

Trial division chockes very fast, For bigger numbers there are trial and error methods as Brent's that can go further.
The code i attach found 600851475143 = [71, 839, 1471, 6857] in 0,1 seconds, but it chokes the same for bigger numbers.
It uses trial division up to 1M then switches to Brent's method.
I can't explain Brent, I just copied the code...

#Py3.4

from fractions import gcd
from random import randint
from time import clock

def brent(N):
   # brent returns a divisor, not guaranteed to be prime
   if N%2==0: return 2
   y,c,m = randint(1, N-1),randint(1, N-1),randint(1, N-1)
   g,r,q = 1,1,1
   while g==1:             
       x = y
       for i in range(r):
          y = ((y*y)%N+c)%N
       k = 0
       while (k<r and g==1):
          ys = y
          for i in range(min(m,r-k)):
             y = ((y*y)%N+c)%N
             q = q*(abs(x-y))%N
          g = gcd(q,N)
          k = k + m
       r = r*2
   if g==N:
       while True:
          ys = ((ys*ys)%N+c)%N
          g = gcd(abs(x-ys),N)
          if g>1:  break
   return g

def factorize(n1):
    if n1<=0: return []
    if n1==1: return [1]
    n=n1
    b=[]
    p=0
    mx=1000000
    while n % 2 ==0 : b.append(2);n//=2
    while n % 3 ==0 : b.append(3);n//=3
    i=5
    inc=2
    while i <=mx:
       while n % i ==0 : b.append(i); n//=i
       i+=inc
       inc=6-inc
    while n>mx:
      p1=n
      #iterate until divisor is prime
      while p1!=p:
          p=p1
          p1=brent(p)
          print(p1)
      b.append(p1);n//=p1 
    if n!=1:b.append(n)
    b.sort()
    return b


from functools import reduce
from sys import argv
def main():
  if len(argv)==2: 
     n=int(argv[1])
  else:  
     n=int(eval(input(" Integer to factorize? ")))
  t1=clock()   
  li=factorize(n)
  print (n,"= ",li)
  print(clock()-t1, " seconds")
  print ("n - product of factors = ",n - reduce(lambda x,y :x*y ,li))

if __name__ == "__main__":
   main()

Python Project Euler 3

3 Answers3