Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.0k views
in Technique[技术] by (71.8m points)

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

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)        
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...