python中的素数生成器:数字的累积 [英] prime number generator in python: accumulation of numbers

问题描述

我的生成器很好用:我已经测试过很多次了.只是，有一个问题:正如人们可能认为的那样，随着数字的增加，程序变得更慢.我已经想到了一种方法来做到这一点，但不知道怎么做，因为我不久前才开始使用 python.

My generator works great: I've tested it many times. Only, there is a problem: as the numbers increase, as one might believe, the program becomes slower. I have thought up of a way to do this, but don't know how, as I have only started with python not too long ago.

我的生成器如下所示:

    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`

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

I have found that if I move the a=[0,1,2] to the space before while 0==0, it accumulates all numbers from previous uses while the program is running. What i want to change about this is that as a accumulates prime numbers, it uses those to catch up to the next unknown number. For example, lets say that I wanted all of the prime numbers up to 100. Then, I wanted all of the prime numbers up to 200. Instead of recalculating the prime numbers up to 100, I want to program to skip those and continue from the first prime number after 100.

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

Any advice will be really appreciated, and I am using 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 中，然后继续.

Alright, I made this program to work so that as the prime numbers are found, they are stored and used for the next set of prime numbers. With this let's say that I wanted to find the primes up to 1000. The program computes the primes. Then, I want to know the primes up to 2000. Well, since the program has already found the primes up to 1000, no need to reproduce them, so it takes all of the prime less than or equal to the highest number is the input, then finds what is left by dividing the new numbers by the known primes. It then adds the new primes to a, and continues.

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

Only thing is, there is a problem. It doesn't want to work the way I planned, and I am working on trying to fix it. Maybe you guys can pitch in and see what is wrong?

好的，我已经编辑了代码以使其运行得更快:

Alright, i have edited the code so that it runs faster:

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 秒.相当升级，如果我可以这样说的话.

So far, this program runs in the fraction of the time as my original and those that i have tried. In a test I preformed, I had it and my first algorithm find all primes to 100000. My first algorithm took a tad bit over 4 minutes, unlike my new program, which took approximately 1 minute and 40 seconds. Quite the upgrade, if I may say so myself.

推荐答案

这应该工作得更快:

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 快得多(见塞巴斯蒂安的评论)，除非你使用更高级的算法和非常庞大的数字 10**100.

But I do not think you can get much faster that O(See comment of sebastian) except if you are using more advanced algorithms and numbers very huge 10**100.

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

It will always get slower with bigger numbers.

这篇关于python中的素数生成器:数字的累积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！