0

我的发电机效果很好：我已经测试过很多次了。只是，有一个问题：随着数字的增加，正如人们所相信的那样，程序变得越来越慢。我已经想到了一种方法来做到这一点，但不知道如何，因为我不久前才开始使用 python。

我的生成器如下所示：

    while 0==0:
        i=input('Enter the number for which all previous shall be tested for primality: ')
        n=0
        a=[0,1,2]
        while n<=i:
            n=n+1
            for b in range(2,n):
                if n%b==0:
                    break
                if b==(n-1):
                    a.append(n)
                    print a`

我发现如果我在 0==0 之前将 a=[0,1,2] 移动到空间，它会在程序运行时累积以前使用的所有数字。我想改变的是，随着素数的累积，它会使用这些素数来赶上下一个未知数。例如，假设我希望所有素数都达到 100。然后，我希望所有素数都达到 200。我不想重新计算最多 100 的素数，而是要编程跳过这些并继续100 之后的第一个素数。

任何建议都将不胜感激，我使用的是 2.7 Python。

a = [2,3,5,7,11]
while 1:
    b = input('Enter the number for which all previous shall be tested for primality: ')
    c = len(a)
    d = 0
    isprime = True
    while b<=a[c-1] and not d==c:
            if b==a[d]:
            print a[0:d]
        if d==(c-1) and not b==a[d]:
            break
        d = d + 1
    while b>a[c-1]:
        d = 0
        print a[c-1]
        if b%a[d]==0:
            isprime = False
            break
        while a[d]==a[c-1]:
            f = a[c-1] + 2
            for g in range(f,b,2):
                if b%g==0:
                    isprime = False
                    break
            if isprime:
                a.append(b)
                print a

好的，我让这个程序工作，以便在找到质数时，将它们存储起来并用于下一组质数。有了这个，假设我想找到最大 1000 的素数。程序计算素数。然后，我想知道 2000 以内的素数。好吧，既然程序已经找到了 1000 以内的素数，就不需要复制它们了，所以它把所有小于或等于最大数的素数作为输入，然后通过将新数字除以已知素数来找到剩下的内容。然后它将新的素数添加到 a，并继续。

唯一的问题是，有一个问题。它不想按我计划的方式工作，我正在努力修复它。也许你们可以参与进来看看有什么问题？

好的，我已经编辑了代码，以便它运行得更快：

While 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=0
    while n<=i:
        n=n+1
        a=int(n**.5)
        for b in range(2,n):
            if n%b==0:
                break
             if b==a:
                print n
                break

到目前为止，这个程序运行的时间只是我原来的和我尝试过的那些时间的一小部分。在我进行的一次测试中，我得到了它，我的第一个算法找到了 100000 的所有素数。我的第一个算法花了 4 分钟多一点，不像我的新程序大约需要 1 分 40 秒。相当升级，如果我自己可以这么说的话。

4

2 回答 2

1

有多种素数算法，其中筛子是最快的。如果您熟悉使用c 扩展 python，则可以包装primesieve。以下是Eratosthenes 筛子的python 实现，如果您还有其他问题，请告诉我：

from __future__ import generators
def eratosthenes():
    '''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
    D = {}  # map composite integers to primes witnessing their compositeness
    q = 2   # first integer to test for primality
    while 1:
        if q not in D:
            yield q        # not marked composite, must be prime
            D[q*q] = [q]   # first multiple of q not already marked
        else:
            for p in D[q]: # move each witness to its next multiple
                D.setdefault(p+q,[]).append(p)
            del D[q]       # no longer need D[q], free memory
        q += 1
于 2013-03-10T18:24:28.390 回答
-1

这应该更快：

while 1:
    i=input('Enter the number for which all previous shall be tested for primality: ')
    n=5
    a=[2,3]
    while n<=i:
        n=n+1
        isPrime = True
        for b in a:
            if n%b==0:
                isPrime = False
                break
        if isPrime:
            a.append(n)
            print a

但我不认为你能比 O（见 sebastian 的评论）更快，除非你使用更高级的算法和非常大的 10**100。

数字越大，它总是会变慢。

于 2013-03-10T11:14:03.440 回答