相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

如何计算多个数字的最小公倍数？

到目前为止,我只能在两个数字之间进行计算.但不知道如何扩展它来计算3个或更多数字.

到目前为止,这就是我做到的

LCM = num1 * num2 /  gcd ( num1 , num2 )

使用gcd是计算数字的最大公约数的函数.使用欧几里得算法

但我无法弄清楚如何计算3个或更多数字.

在任何人开始之前,我知道在编程语言中谈论"速度"并不总是最有用的讨论.也就是说,速度是这里的问题.

我用两种语言解决了Project Euler问题5,虽然我在两种语言中的实现看起来与我的眼睛非常相似,但运行时却大不相同.Java只需几秒钟即可返回答案,而Python最多可能需要一分钟(当然,在同一台机器上).我很确定这不是Python的错,更不是程序员(我)的错,他们还没有学会用Python来学习.

请注意,我不是要求您重写我的代码.我只是在朝着正确的方向寻找一些推动力.(是的,我看过一些 类似的 线程,但大多数都是我的头脑,并没有直接比较两种语言中的相同算法.这个线程很有用,但同样,不直接比较Java和Python -坦率地说,答案有点难以理解.)

无需再费周折:

Java的

public class Problem5 {

    public static void main(String[] args){
        boolean found = false;

        for (int i = 20; !found; i += 20){
            if (DivisThrough20(i)) {
                found = true;
                System.out.println(i);
            }
        }
    }

    private static boolean DivisThrough20(int number){
        boolean result = true;
        for (int i = 19; result && i > 1; i--){
            if (number % i != 0) result = false;
        }
        return …

我把这个解决方案写给Project Euler#5.

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

    a = m
    start = 2
    while (m % start) == 0:
        start += 1

    b = start
    while b < m:
        if ( a % b) != 0:
           a += m
           b = start
           continue
        else:
            b += 1
    return a

import sys

if (len(sys.argv)) > 2:
    print "error: this function takes a max of 1 argument"
elif (len(sys.argv)) == 2:
    print ProjectEulerFive(int(sys.argv[1]))
else:                          
    print …

我正在尝试解决下面详述的项目拼图.我当前的函数适用于数字1到10,但是当我尝试1到20时,它只是永远循环而没有结果.

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

def calculate():
    results = dict()
    target = 20
    num_to_test = 1
    while len(results) < target:
        for j in range(1, target+1):
            results[num_to_test] = True
            if num_to_test % j != 0:
                # current num_to_test failed in the 1-10, move on
                del results[num_to_test]
                break

        num_to_test += 1
    return min(results)

任何人都可以在逻辑中看到任何问题,特别是我想知道为什么它适用于10的目标,但不是20.谢谢