卡在python项目Euler#3上 [英] Stuck on Project Euler #3 in python

问题描述

13195的主要因子是5、7、13和29.最大的因子是多少 600851475143的素数?

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

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

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?\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)        

谢谢！

推荐答案

• 数字600851475143很大，不鼓励您使用蛮力.
• oddNumbers函数用于将600851475143 / 2数字放入odd_list，这将很多.
• 检查数字是否可以除以奇数并不意味着该奇数是质数.您提供的算法有误.
• 有很多关于素数的数学/算法技巧，您应该先在线搜索它们，然后筛选答案.您还可能会扎根问题，以确保您已经解决一些问题.
• the number 600851475143 is big to discourage you to use brute-force.
• the oddNumbers function in going to put 600851475143 / 2 numbers in odd_list, that's a lot of memory.
• checking that a number can be divided by an odd number does not mean the odd number is a prime number. the algorithm you provided is wrong.
• there are a lot of mathematical/algorithm tricks about prime numbers, you should and search them online then sieve through the answers. you might also get to the root of the problem to make sure you have squared away some of the issues.

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

you could use a generator to get the list of odds (not that it will help you):

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

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

here are the concepts needed to deal with prime numbers:

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

如果您真的受困，那么已经有解决方案了:

if you are really stuck, then there are solutions already there:

• Project Euler#3，无限循环因式分解
• Project Euler 3-为什么这种方法有效?
• Project Euler问题3帮助
• Project Euler #3, infinite loop on factorization
• Project Euler 3 - Why does this method work?
• Project Euler Question 3 Help

这篇关于卡在python项目Euler#3上的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！