3

我目前正在尝试使用 Python 解决 Project Euler 问题（我今天才学到的东西）。我正在处理的问题是问题 5，其中

2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。

能被 1 到 20 的所有数整除的最小正数是多少？

我以前使用 Java 解决过这些问题，所以使用与以前相同的方法，我只是创建了一个迭代的循环，但是我的代码似乎永远不会结束。

Python：

i = 1
while 1:
    if i%2 == 0 and i%3==0 and i%4==0 and i%5==0 and i%6==0 and i%7==0 and i%8==0 and i%9==0 and i%10==0 and i%11==0 and i%12==0 and i%13==0 and i%14==0 and i%15==0 and i%16==0 and i%17==0 and i%18==0 and i%19==0:
        print i
        break
    i+=1

爪哇：

public class p5
{
    public static void main(String[] args)
    {
        for (int i=1;;i++)
        {
            if (i%1==0&&i%2==0&&i%3==0&&i%4==0&&i%5==0&&i%6==0&&i%7==0&&i%8==0&&i%9==0&&i%10==0&&i%11==0&&i%12==0&&i%13==0&&i%14==0&&i%15==0&&i%16==0&&i%17==0&&i%18==0&&i%19==0&&i%20==0)
            {
                System.out.println(i);
                break;
            }
        }
    }
}

Java 在我的计算机上执行了不到 3 秒，而 Python 代码似乎从未结束。有小费吗？

编辑：

显然我输入了错误的东西，导致它永远不会结束。但是，即使正确编写了整个内容（与我的 Java 具有相同的输出），它仍然需要1 分 20 秒，而对于 Java，它需要大约 1-2 秒。我做错什么了吗？还是 Python 的性能那么差（这不应该是 afaik）

4

2 回答 2

4

在 Java 中使用原始 s 的算术比使用intCPython 中的完整整数对象快得多，即，您看到的 30 倍的性能差异对于您的代码来说并不奇怪。

请注意，该算法效率非常低，并且不适用于稍大的输入，例如，对于从 1 到 50 的数字（它花费的时间太长，并且正确的结果大于 Java 中的 max int/long）。

使用更有效的算法计算我的机器上从 1 到 100 的所有数字的结果需要 ~100 微秒：

#!/usr/bin/env python
from functools import reduce

def gcd(a, b):
    """Greatest common divisor (factor)."""
    while b: # Euclid's algorithm
        a, b = b, a % b
    return a

def lcm(*args):
    """Least common multiple."""
    # lcm(a, b, c) == lcm(lcm(a, b), c)
    return reduce(lambda a, b: a * b // gcd(a, b), args)

def f(n):
    """Smallest positive number evenly divisible by all numbers from 1
       to n including.
    """
    return lcm(*range(1, n + 1))

print(f(10)) # -> 2520
print(f(50)) # -> 3099044504245996706400

估计 性能：

#!/usr/bin/env python
import timeit
from functools import partial

def measure():
    for n in [10, 50, 100]:
        print("%d: %5.2f microseconds" % (n, timeit.timeit(partial(f, n),
                                                           number=1000*1000)))
measure()
于 2012-10-24T19:09:14.950 回答
2

我的纯蛮力解决方案使用 pypy 大约需要 250 毫秒：

i = 20
while 1:
    if i%20 == 0 and i%19==0 and i%18==0 and i%17==0 and i%16==0 and i%15==0 and i%14==0 and i%13==0 and i%12==0 and i%11==0:
        print i
        break
    i+=20

更优雅的应该使用最大公约数和最小公约数之类的东西。

于 2012-10-24T15:17:50.917 回答