相关疑难解决方法(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

只是为了澄清,这不是一个功课问题:)

我想找到我正在建造的数学应用程序的素数并且遇到了Eratosthenes的Sieve方法.

我用Python编写了它的实现.但它非常慢.比方说,如果我想找到不到200万的所有素数.大约需要20分钟.(此时我停了下来).我怎样才能加快速度呢？

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

更新: 我最终对这段代码进行了分析,发现花了很多时间从列表中删除一个元素.考虑到它必须遍历整个列表(最坏情况)才能找到元素然后将其删除然后重新调整列表(可能还有一些副本继续？),这是相当容易理解的.无论如何,我把字典列表删掉了.我的新实施 -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

我是编程和python的新手.我正在解决一个问题.我找到了解决方案,但似乎太慢了.

    if n % 2 == 0 and n % 3 == 0 and\
       n % 4 == 0 and n % 5 == 0 and\
       n % 6 == 0 and n % 7 == 0 and\
       n % 8 == 0 and n % 9 == 0 and\
       n % 10 == 0 and n % 11 == 0 and\
       n % 12 == 0 and n % 13 == 0 and\
       n % 14 == 0 and …