math - Stuck on Project Euler #3 in python

Question

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

Ok, so i am working on project euler problem 3 in python. I am kind of confused. I can't tell if the answers that i am getting with this program are correct or not. If somone could please tell me what im doing wrong it would be great!

#import pdb

odd_list=[]
prime_list=[2] #Begin with zero so that we can pop later without errors.

#Define a function that finds all the odd numbers in the range of a number
def oddNumbers(x):

  x+=1 #add one to the number because range does not include it
  for i in range(x):
     if i%2!=0: #If it cannot be evenly divided by two it is eliminated
        odd_list.append(i) #Add it too the list
    
  return odd_list 

def findPrimes(number_to_test, list_of_odd_numbers_in_tested_number): # Pass in the prime number to test
   for i in list_of_odd_numbers_in_tested_number:
     if number_to_test % i==0:
       prime_list.append(i)
       number_to_test=number_to_test / i
          
       #prime_list.append(i)
       #prime_list.pop(-2) #remove the old number so that we only have the biggest

       if prime_list==[1]:
           print "This has no prime factors other than 1"
       else:
           print prime_list
       return prime_list
        
    #pdb.set_trace()

    number_to_test=raw_input("What number would you like to find the greatest prime of?
:")

    #Convert the input to an integer
    number_to_test=int(number_to_test)

    #Pass the number to the oddnumbers function
    odds=oddNumbers(number_to_test)

#Pass the return of the oddnumbers function to the findPrimes function
findPrimes(number_to_test , odds)        

Answer 1

The simple solution is trial division. Let's work through the factorization of 13195, then you can apply that method to the larger number that interests you.

Start with a trial divisor of 2; 13195 divided by 2 leaves a remainder of 1, so 2 does not divide 13195, and we can go on to the next trial divisor. Next we try 3, but that leaves a remainder of 1; then we try 4, but that leaves a remainder of 3. The next trial divisor is 5, and that does divide 13195, so we output 5 as a factor of 13195, reduce the original number to 2639 = 13195 / 5, and try 5 again. Now 2639 divided by 5 leaves a remainder of 4, so we advance to 6, which leaves a remainder of 5, then we advance to 7, which does divide 2639, so we output 7 as a factor of 2639 (and also a factor of 13195) and reduce the original number again to 377 = 2639 / 7. Now we try 7 again, but it fails to divide 377, as does 8, and 9, and 10, and 11, and 12, but 13 divides 2639. So we output 13 as a divisor of 377 (and of 2639 and 13195) and reduce the original number again to 29 = 377 / 13. As this point we are finished, because the square of the trial divisor, which is still 13, is greater than the remaining number, 29, which proves that 29 is prime; that is so because if n=pq, then either p or q must be less than, or equal to the square root of n, and since we have tried all those divisors, the remaining number, 29, must be prime. Thus, 13195 = 5 * 7 * 13 * 29.

Here's a pseudocode description of the algorithm:

function factors(n)
    f = 2
    while f * f <= n
        if f divides n
            output f
            n = n / f
        else
            f = f + 1
    output n

There are better ways to factor integers. But this method is sufficient for Project Euler #3, and for many other factorization projects as well. If you want to learn more about prime numbers and factorization, I modestly recommend the essay Programming with Prime Numbers at my blog, which among other things has a python implementation of the algorithm described above.