Here is my attempt at solving Project Euler problem 3. It works for test numbers up to 9 digits long, but overflows when I input the real 12-digit behemoth.
I've looked at other methods of solution, but I wanted to challenge myself to code one that doesn't search with unnecessary numbers - only primes - and never any of their factors.
I would sincerely appreciate it if someone with more coding experience could show me where in my program I am taking up a lot of memory/computational efficiency/etc.
#The prime factors of 13195 are 5, 7, 13 and 29.
#What is the largest prime factor of the number 600851475143 ?
import numpy as np
import math
def lpf(n):
orig=n #Store the original n as a reference.
ceiling=int(math.floor(np.sqrt(n)))+1 #Don't check for prime factors larger than sqrt(n).
thelist=[]
for i in xrange(2,ceiling):
thelist.append(i) #Make a list of integers from 2 up to floor(sqrt(n))+1.
plist=[2] #Initialize a running list of primes.
pfpairs=[] #Initialize a list to store (prime factor, multiplicity) pairs.
removed=[] #Initialize a list to store removed prime multiples.
for p in plist:
if p>=ceiling: #Again, don't check for prime factors larger than sqrt(n).
break
i=2
pexp=0 #Set the multiplicity of the prime to zero initially.
if n%p==0: #If the prime divides n, set the new n to n/p and see if it divides again.
#print n, p
pexp=1
n=n//p
while True:
if n%p==0: #As long as there is no remainder after division by p, keep dividing n by p,
n=n//p #making sure to redefine n and increment p's multiplicity with each successful divison.
pexp+=1
else:
pfpairs.append((p,pexp)) #Once a divison fails, store the prime and its multiplicity.
break
while (p*i)<=ceiling: #As long as the prime multiples dont exceed the ceiling,
if (p*i) in removed: #if the current multiple has already been removed, move on.
i+=1
elif (p*i) not in thelist:
i+=1
else:
removed.append(p*i) #Else, add that multiple to the removed pile, and then remove it from the list.
thelist.remove(p*i)
i+=1
for number in thelist: #After all prime multiples (not including p*1) are deleted from the list,
if number>p: #the next number in the list larger than p is guaranteed to be prime, so set
plist.append(number) #p to this new number and go through the logic again.
break
print '%d =' % orig, #Print the prime factorization of n to the user.
for pair in pfpairs:
if pair != pfpairs[-1]:
print '(%d^%d) x' % (pair[0], pair[1]),
if pair == pfpairs[-1]:
print '(%d^%d)' % (pair[0], pair[1])
return max(pfpairs, key = lambda pair: pair[0])[0] #Return the largest prime factor.
print lpf(78618449)
>>>
78618449 = (7^1) x (13^1) x (29^1) x (31^3)
31