Python中的Euler 5项目 - 如何优化我的解决方案？

Question

我最近一直在研究Python中的Project Euler问题.我对Python很陌生,作为程序员还是有点新鲜.

无论如何,我遇到了与速度相关的问题,为问题#5编写了解决方案.问题是,

"2520是可以除以1到10之间的每个数字而没有任何余数的最小数字.可以被1到20的所有数字整除的最小正数是多少？"

我已经检查了一些,我无法找到任何与Python有关的问题.有一些已完成的脚本,但我想避免完全查看其他代码,如果可能的话,而不是想改进我自己的代码.

我编写的代码成功运行2520的示例和范围1到10,并且应该可以直接修改以处理问题.但是,在运行它时,我没有得到答案.据推测,这是一个非常高的数字,代码不够快.打印正在检查的当前号码似乎支持这一点,达到数百万而没有得到答案.

代码,在它的当前实现如下:

rangemax = 20
def div_check(n):
    for i in xrange(11,rangemax+1):
        if n % i == 0:
            continue
        else:
            return False
    return True

if __name__ == '__main__':
   num = 2
   while not div_check(num):
       print num
       num += 2
   print num

我已经做了一些改变,我认为应该有助于提高速度.首先,对于一个数字可以被所有数字1到20整除,它必须是偶数,因为只有偶数可以被2整除.因此,我可以增加2而不是1.此外,虽然我没有想到我自己,我发现有人指出一个可以被11到20整除的数字可以被1到10整除.(没有检查那个,但似乎合理)

但代码仍然不够快.我可以进行哪些优化(程序化或数学)来使这段代码运行得更快？

提前感谢任何可以提供帮助的人.

Answer 1

根据迈克尔·米奥的建议和捅,我写了一个解决方案.我尝试使用一些技巧来加快速度.

由于我们需要一个相对较短的数字列表,因此我们可以预先建立数字列表而不是重复调用xrange()或range().

此外,虽然将数字[1, 2, 3, ..., 20]放在列表中会起作用,但我们可以稍微思考一下,并将数字拉出来:

只需拿出1.每个整数都可以被1整除.

如果我们离开20,则不需要将2输入.任何可被20整除的整数均可被2整除(但反之可能不是这样).所以我们离开20并取出2,4和5.离开19,因为它是素数.离开18,但现在我们可以取出3和6.如果你重复这个过程,你最终会得到一个更短的数字列表来尝试.

迈克尔·米奥建议,我们从20开始,步数到20.all()正如poke建议的那样,我们在其中使用生成器表达式.

而不是while循环,我用了一个for循环xrange(); 我认为这稍快一些.

结果:

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

在我的电脑上,这会在九秒钟内找到答案.

编辑:而且,如果我们接受David Zaslavsky的建议,我们意识到我们可以在2520开始循环,然后步骤2520.如果我这样做,那么在我的计算机上,我会在大约十分之一秒内得到正确答案.

我提出了find_solution()一个论点.试着打电话find_solution(2520).

Answer 2

我的第一个答案加快了问题的原始计算.

这是另一个以不同的方式解决它的答案:找到每个数字的所有素因子,然后将它们相乘以直接得到答案.换句话说,这会在评论中自动化poke推荐的过程.

它在几分之一秒内完成.我认为没有更快的方法来做到这一点.

我在Google上搜索了"找到素数因子Python"并发现了这个:

http://www.stealthcopter.com/blog/2009/11/python-factors-of-a-number/

从那里我找到了一个链接factor.py(由Mike Hansen编写)和一些有用的功能:

http://sage.math.washington.edu/home/mhansen/factor.py

他的功能并没有达到我想要的水平,所以我写了一个新的功能,但用他pull_prime_factors()做了艰苦的工作.结果是find_prime_factors()返回元组列表:素数和计数.例如,find_prime_factors(400)返回[(2,4), (5,2)]因为400的素数因子是:(2*2*2*2)*(5*5)

然后我用一个简单的方法defaultdict()来跟踪我们到目前为止看到的每个素数因子.

最后,循环将所有内容相乘.

from collections import defaultdict
from factor import pull_off_factors

pf = defaultdict(int)

_primes = [2,3,5,7,11,13,17,19,23,29]
def find_prime_factors(n):
    lst = []
    for p in _primes:
        n = pull_off_factors(n, p, lst)
    return lst

def find_solution(low, high):
    for num in xrange(low, high+1):
        lst = find_prime_factors(num)
        for n, count in lst:
            pf[n] = max(pf[n], count)

    print "prime factors:", pf
    solution = 1
    for n, count in pf.items():
        solution *= n**count

    return solution

if __name__ == '__main__':
    solution = find_solution(1, 20)
    print "answer:", solution

编辑:哦,哇,我刚刚看了@JF Sebastian对相关问题的回答.他的回答与上面的代码基本相同,只是更加简单和优雅.事实上它比上面的代码更快.

3个或更多数字的最小公倍数

我将保留上述内容,因为我认为这些函数可能在Project Euler中有其他用途.但这是JF Sebastian解决方案:

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

def lcm_seq(seq):
    """Return lcm of sequence."""
    return reduce(lcm, seq)

solution = lcm_seq(xrange(1,21))
print "lcm_seq():", solution

我补充说lcm_seq()你也可以打电话:

lcmm(*range(1, 21))

Answer 3

由于你的答案必须可以被20整除,你可以从20开始,然后增加20而不是2.一般来说,你可以从...开始rangemax并递增rangemax.这减少了一个数量级的div_check调用次数.