Euler Problem 3 Python Solution

The problem is to find the largest prime factor of 600851475143.

Some ugly python and an ugly solution. Clearly not very computationally efficient as I’m recalculating primes each time. There are also other computationally more efficient solutions out there in any case. This is just here for my reference:

import math

def getprimes(input):
  i = input #math.sqrt(input)

  vals = range(2,int(i))

  for n in vals:
    for j in xrange(n+n,int(i),n):
      if j in vals:
        vals.remove(j)

  vals.reverse()
  return vals

input = 600851475143L

primes_max = 100

while 1:
  primes = getprimes(primes_max)
  #print primes
  p = 0
  for i in primes:
    if input%i == 0:
      print "factor: ",i
      input = input/i
      p = 1


  if primes_max > math.sqrt(input):
    if p == 0:
      print "factor: ",input
      break

  primes_max = primes_max + 1000
  print primes_max

One thought on “Euler Problem 3 Python Solution

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>