卡住在項目歐拉＃3 python

Question

13195的主要因素是5,7,13和29.什麼是最大的 數字600851475143的主要因素？

好的，所以我正在處理python中的項目歐羅問題3。我有點困惑。我無法判斷我得到的答案是否正確。如果somone可以告訴我什麼即時做錯了，那會很棒！

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

謝謝！

Answer 1

• 數字600851475143是大的阻止你使用蠻力。
• oddNumbers功能在去600851475143/2號碼在odd_list，這就是很多的內存。
• 檢查一個數字是否可以被一個奇數分開並不意味着該奇數是一個素數。你提供的算法是錯誤的。
• 有很多關於素數的數學/算法技巧，你應該在網上搜索他們然後通過篩選答案。你也可能會得到到根目錄的問題，以確保你有擺脫了的一些問題。

你可以使用一個發電機來獲得優勢（而不是它會幫助你）的列表：

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

這裏是處理質數所需的概念：

• http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
• http://en.wikipedia.org/wiki/Primality_test

如果你真的卡住，則也有解決方案已經存在：

• Project Euler #3, infinite loop on factorization
• Project Euler 3 - Why does this method work?
• Project Euler Question 3 Help

Answer 2

簡單的解決辦法就是審判庭。讓我們通過13195的分解工作，然後您可以將該方法應用於您感興趣的更大數字。

以2的試驗除數開始; 13195除以2剩下的1，所以2不等於13195，我們可以繼續下一個試驗除數。接下來我們嘗試3，但剩下1;那麼我們嘗試4，但剩下的是3。下一個試驗除數是5，這確實將13195分開，所以我們輸出5作爲13195的因子，將原始數減少到2639 = 13195/5，並嘗試5再次。現在2639除以5剩下的4，所以我們前進到6，剩下的5，然後我們前進到7，這將除以2639，所以我們輸出7爲2639的因子（也是因子13195）並將原始數字再次減少到377 = 2639/7。現在我們再次嘗試7，但它沒有分割377，8和9，10和11和12，13除2639，所以我們輸出13作爲除數377（和2639和13195）並且將原始數字再次減少到29 = 377/13。由於這一點我們完成了，因爲仍然是13的試驗除數的平方大於剩餘的數字29，這證明了29是素數;那是因爲，如果N = PQ，然後要麼p或q必須小於或等於n的平方根，並且由於我們已經嘗試了所有這些除數，剩餘數量，29，必須成爲素數。因此，13195 = 5 * 7 * 13 * 29

這裏的算法的僞代碼描述：

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

有更好的方法對因子整數。但是這種方法對Project Euler＃3以及許多其他分解項目也是足夠的。如果你想了解更多關於素數和分解的知識，我在我的博客中謙虛地推薦文章Programming with Prime Numbers，其中還包括上述算法的python實現。

Answer 3

''' 
The prime factors of 13195 are 5, 7, 13 and 29. 

What is the largest prime factor of the number 600851475143 ? 
''' 
import math 

def isPrime(x): 
    if x<2: 
     return False 
    for i in range(2,int(math.sqrt(x))): 
     if not x%i: 
      return False 
    return True 

def largest_factor(number): 
    for i in range (2, int(math.sqrt(number))): 
     if number%i == 0: 
      number = number/i 
      if isPrime(number) is True: 
       max_val = number 
       break 
       print max_val 
     else: 
      i += 1 
    return max_val 

largest_factor(600851475143) 

這實際上編譯速度非常快。它檢查是否爲素數形成的數字。 感謝

Answer 4

這裏是我的Python代碼：

num=600851475143 
i=2 # Smallest prime factor 
for k in range(0,num): 
    if i >= num: # Prime factor of the number should not be greater than the number 
     break 
    elif num % i == 0: # Check if the number is evenly divisible by i 
     num = num/i 
    else: 
     i= i + 1 
print ("biggest prime number is: "+str(num)) 

Answer 5

另一種解決方案，以使用Python這個問題。

def lpf(x): 
lpf=2 
while (x>lpf): 
    if (x%lpf==0): 
     x=x/lpf 

    else: 
     lpf+=1 
return x 
print(lpf(600851475143))