一尘不染

卡在python项目Euler#3上

python

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)

阅读 210

收藏
2021-01-20

共1个答案

一尘不染

  • 这个数字600851475143很大,不鼓励您使用蛮力。
  • oddNumbers在打算把功能600851475143 / 2号码odd_list,这是 一个很大 的内存。
  • 检查数字是否可以除以奇数并不意味着该奇数是质数。您提供的算法有误。
  • 关于质数,有很多数学/算法技巧,您应该在线搜索并 筛选 答案。您可能还会找到问题 的根源 ,以确保已解决 一些问题。

您可以使用生成器来获取赔率列表(并非对您有帮助):

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

以下是处理质数所需的概念:

2021-01-20