user1074202 user1074202 - 1 year ago 58
Python Question

Stuck on Project Euler #3 in python

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

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:
number_to_test=number_to_test / 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"
print prime_list
return prime_list


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

#Convert the input to an integer

#Pass the number to the oddnumbers function

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

Thank You!!

Answer Source
  • the number 600851475143 is big to discourage you to use brute-force.
  • the oddNumbers function in going to put 600851475143 / 2 numbers in odd_list, that's a lot of memory.
  • checking that a number can be divided by an odd number does not mean the odd number is a prime number. the algorithm you provided is wrong.
  • there are a lot of mathematical/algorithm tricks about prime numbers, you should and search them online then sieve through the answers. you might also get to the root of the problem to make sure you have squared away some of the issues.

you could use a generator to get the list of odds (not that it will help you):

odd_list = xrange(1, number+1, 2)

here are the concepts needed to deal with prime numbers:

if you are really stuck, then there are solutions already there: