#Project Euler Problem 3:
#What is the largest prime factor of the number 600851475143 ?

import time
start = time.time()

from math import sqrt

n = 600851475143
m = n
bigO = 0
prime_factors = []

print "n=", n
print "--------"

#Check if 2 is a factor:
while m%2 == 0:
  print "i = 2, m = ", m
  print "Factor: 2"
  prime_factors.append(2)
  m = m/2
  bigO += 1

#Continue with the rest of the odd naturals less than m (which is n with all powers of 2 removed to begin with):
i = 3
while i <= m:
  #print "i = " + str(i) +", m = " + str(m)
  if m%i == 0:
    #print "Factor: " , i
    prime_factors.append(i)
    m = m/i
    i -= 2 
  i += 2
  bigO += 1

#if n%m == 0:
#  print "m=", m

print "Prime decomposition: ", prime_factors
print "Iterations: ", bigO
print "Total elapsed time: " + str((time.time()-start)*1000) + " milliseconds."

n= 600851475143
--------
Prime decomposition:  [71, 839, 1471, 6857]
Iterations:  3431
Total elapsed time: 9.62114334106 milliseconds.