卡在python项目Euler＃3上

Question

13195的素数是5、7、13和29。600851475143的最大素数是多少？

好的，所以我正在研究python中的项目Euler问题3。我有点困惑。我无法确定我通过该程序获得的答案是否正确。如果有人能告诉我即时消息做错了，那太好了！

#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

如果您 真的 被卡住了，那么已经有解决方案了：

• 项目Euler＃3，因式分解的无限循环
• 欧拉计画3-这种方法为何有效？
• 欧拉项目问题3帮助