Take the 2-minute tour ×

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!!

share|improve this question
Its not neccessary that every one has solved Project Euler # 3. At least post the problem statement here. And you need to tell us what's the problem with your code, rather than asking anyone. –  Rohit Jain Oct 21 '12 at 16:23
"I can't tell if the answers that i am getting with this program are correct or not." Testing a factorization program is easy: just multiply the factors and see if the result matches the original number. –  hammar Oct 21 '12 at 16:36
try the sieve algorithm for primes, otherwise brute force is going to take a long long time for 600851475143. –  Aशwini चhaudhary Oct 21 '12 at 17:04
@hammar not if the factors are produced without their multiplicities, which is nevertheless OK for the Q at hand. –  Will Ness Oct 22 '12 at 7:48
@AshwiniChaudhary brute force should take no more than few seconds for this problem, if you (correctly) stop at 775146. –  Will Ness Oct 22 '12 at 7:55
add comment

2 Answers

up vote 3 down vote accepted
  • 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:

share|improve this answer
even brute-force works for such small numbers. +1 for "sieve through answer" and "squared away" –  J.F. Sebastian Oct 21 '12 at 17:17
-1 this is not a stand-up comedy forum (re: "search online and sieve through the answers" and "get to the root ... squared away the issues"). Sending an OP on the wild goose, erhm, google search chase is expressly frowned upon here on SO. IOW, saying "go search for it on the interwebs" (without even saying what "it" is) is not an answer. And the proper place to post links to other SO answers is in the comments. –  Will Ness Oct 22 '12 at 7:37
@Will Ness, Project Euler is about challenges, so hints rather than spoilers are appropriate. Please don't decide where the proper place for links is by yourself and respect other users. –  dnozay Oct 22 '12 at 15:53
I meant no disrespect, sorry if it looked that way. It's just that your hints were encoded too deeply, and I mistook them for smug remarks rather than hints, such that the others "in the know" will understand but the OP had no chance of understanding or even recognizing them as hints. My bad, I overreacted. As for links, I specifically talked about links to SO answers only. Now, with new emphasis and WP links, it has much better chance to help the OP. –  Will Ness Oct 22 '12 at 16:17
add comment

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
            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.

share|improve this answer
92365 = 5 * 7 * 7 * 13 * 29 would be a better choice to showcase the algorithm IMO. :) But kudos for the clear and detailed exposition! –  Will Ness Oct 22 '12 at 8:04
add comment

Your Answer


