user1074202 - 1 year ago 66

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?\n:")

#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)

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: