在python中坚持项目Euler#3

Question

13195的主要因素是5,7,13和29. 600851475143中最大的素数是多少？

好的,所以我正在研究python中的项目euler问题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

简单的解决方案是试验分工.让我们通过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以及许多其他分解项目来说已经足够了.如果你想了解更多关于素数和因子分解的信息,我谦虚地推荐在我的博客上使用素数编程的文章,其中包括上述算法的python实现.

Answer 2

• 这个数字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，因式分解的无限循环
• Project Euler 3 - 为什么这种方法有效？
• Project Euler 问题 3 帮助