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= #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, pair), if pair == pfpairs[-1]: print '(%d^%d)' % (pair, pair) return max(pfpairs, key = lambda pair: pair) #Return the largest prime factor. print lpf(78618449) >>> 78618449 = (7^1) x (13^1) x (29^1) x (31^3) 31