#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."