素数序列发生器

Question

我刚刚开始使用Python，我正在尝试制作一个素数序列生成器，它将在终端中打印指定数量的素数。我还有其他版本，还有Fibonacci序列的版本，不过，我将只发布我上面指定的素数的版本。

    P = 2
    Count = 1
    X = int(raw_input('choose number: '))

    def Main(P, X):
        while Count <= X:
            isprime = True
            for x in range(2, P - 1):
                if P % x == 0: 
                    isprime = False
            if isprime:
                print P
                Count += 1
            P += 1

我目前正在努力优化这段代码，以便它能够尽可能快地运行，然后进行小的编辑。我这样做的方法是在序列生成器的开始和结尾放置一个get日间函数，然后打印时间，然后循环所有指定的时间。

from datetime import datetime as dt

P = 2
Count = 1
Count2 = 1
X = int(raw_input('choose number: '))

def Main(P, Count, X):
    t1 = dt.now()
    while Count <= X:
        isprime = True
        for x in range(2, P - 1):
            if P % x == 0: 
                isprime = False
        if isprime:
            Count += 1
        P += 1
    t2 = dt.now()
    print ((t2-t1).microseconds)

while Count2 <= 20:
    Main(P, Count, X)
    Count2 += 1

就我对Python的了解而言，我已经优化了这段代码，使其运行效率相当高。但是，我想知道是否有人可以帮助使这段代码变得更好，但是，它需要保持在一个函数内(如果需要的话是两个)，并且它做的是相同类型的事情。此外，如果有可能解释为什么它做得更好，那将是非常感谢的。不过，任何评论或反馈都会很好。

Answer 1

这里的一个逻辑优化是记住您已经计算过的素数。考虑一下这个理论：

素数是一个可以被它自己整除的数，并且只有1。

因此，要检验任何数字X是否是素数，只需要找到一个小于X的素数，它除以X，没有余数。不需要测试非素数，因为如果一个非素数干净地划分为X，那么素因子也会除以X。

因此，如果您保存了先前计算出的素数的记录，那么您只需扫描这些值，看看它们是否除以X。本质上，每次打印质数时，也要将它添加到列表中。

这将需要使用值为2的主列表“种子”。

第二个优化是，一个数字X只有在它有一个因子的情况下才是素数。因数是一个数，乘以另一个数，等于原值X。

这里有用的理论是，当第一个因子的值增加时，第二个因子的值就会减小。当第一个和第二个因素“交叉”时，第二个因素变得比第一个因素要小。

交叉点是数字X的平方根。当您传递数字的平方根时，您已经测试了所有可能的因素.没有必要扫描大于根的值，因为如果它们是因子，您就已经通过识别匹配较大因子的小因子来找到它们了。

将这两个项放在一起，您应该将代码修改为：

1. 对于2有一个特例，它是素数，并将其存储在种子数组中。
2. 保留在同一数组中找到的素数。
3. 对于大于2的值，只需使用预先标识的素数数组中的值来测试因素。
4. 您只需要查找小于或等于值的平方根的素因子。

Answer 2

由于滚转对算法进行了很好的回顾，我将重点介绍您提供的实际代码。

风格

您的变量和函数名并不完全符合PEP 8风格的指南。

count，p，main等可能会更好。而且，main不是一个好名字，generate_prime可能更好。

而且，您使用Count2所做的事情可以更简单地通过一个for循环来完成。因为没有使用用于迭代的数字，所以惯例是将其命名为_，我们有：for _ in range(20)，它将执行您想要执行的任何操作20次。

此时，您的代码如下所示：

from datetime import datetime as dt

def generate_primes(p, count, x):
    t1 = dt.now()
    while count <= x:
        isprime = True
        for i in range(2, p - 1):
            if p % i == 0:
                isprime = False
        if isprime:
            count += 1
        p += 1
    t2 = dt.now()
    # Commented for testing purposes : print ((t2-t1).microseconds)

if __name__ == "__main__":
    p = 2
    count = 1
    x = 11 # Commented for testing purposes : int(raw_input('choose number: '))
    for _ in range(20):
        generate_primes(p, count, x)

函数的

分解

您有一段代码来测试数字是否是素数。这可以很容易地提取到一个函数本身，您将能够重用和/或优化以后。

def is_prime(n):
    isprime = True
    for i in range(2, n - 1):
        if n % i == 0:
            isprime = False
    return isprime

def generate_primes(p, count, x):
    t1 = dt.now()
    while count <= x:
        if is_prime(p):
            print(p)
            count += 1
        p += 1
    t2 = dt.now()
    # Commented for testing purposes : print ((t2-t1).microseconds)

全局变量

目前，您的主要函数使用全局变量，因此很难跟踪它应该做的事情，也很难进行测试。

似乎您正在尝试使用这个变量做多件事情:跟踪计数、检查限制和跟踪您必须考虑的数字。对于一个函数来说，这是相当多的工作。

Python有一个非常酷的特性，它可以帮助您以更好的方式编写东西：发电机。我们可以定义一种函数，它会在每次调用它时生成一个新的素数，然后将它称为正确的次数。

您可以迭代这样一个函数的结果，就像在容器上迭代一样，但是您必须记住，它不会结束，除非您显式地这样做。

例如，您可能会有这样的情况：

def generate_primes():
    p = 2
    while True: # never ending loop
        if is_prime(p):
            yield p
        p += 1


i = 0
for p in generate_primes():
    print(p)
    i+=1
    if i == 10:
        break

我们有把问题分开：一方面，我们有一个素数发生器，另一方面，有一些逻辑来计算它们。

既然你有了基础，我们就可以改进这一点了。例如，我们可以使用zip和range来确保我们只从素数生成器中提取有限数量的元素。

for i, p in zip(range(10), generate_primes()):
    print(i, p)

此外，在函数本身中，我们可以使用itertools.count以更快、更简洁的方式遍历p的值。

您的代码现在看起来如下：

from datetime import datetime as dt
import itertools

def is_prime(n):
    isprime = True
    for i in range(2, n - 1):
        if n % i == 0:
            isprime = False
    return isprime

def generate_primes():
    for p in itertools.count(2):
        if is_prime(p):
            yield p

if __name__ == "__main__":
    lim = 11 # Commented for testing purposes : int(raw_input('choose number: '))
    for _ in range(20):
        t1 = dt.now()
        zip(range(10), generate_primes())
        t2 = dt.now()
        print ((t2-t1).microseconds)

各种优化

作为参考，目前，在我的配置上生成1000个素数大约需要366000微秒.

在is_prime中，一旦设置了isprime = False，就可以从函数返回，因为它永远不会返回到True。您可以简单地删除变量并直接调用return：

def is_prime(n):
    for i in range(2, n - 1):
        if n % i == 0:
            return False
    return True

我刚刚意识到，由于您使用的是Python2，所以只需调用xrange而不是range，因为不需要生成列表。运行时间降到146000.

现在，如果n不是素数，那么至少一个除数将更小或等于它的平方根。因此，您可以这样做：

import math

def is_prime(n):
    for i in xrange(2, 1 + int(math.sqrt(n))):
        if n % i == 0:
            return False
    return True

运行时间减少到7000.

当你迭代寻找素数时，你知道除了2，它们都是奇数。您可以生成2，然后只遍历奇数：

def is_prime(n):
    for i in xrange(2, 1 + int(math.sqrt(n))):
        if n % i == 0:
            return False
    return True

def generate_primes():
    yield 2
    for p in itertools.count(3, 2):
        if is_prime(p):
            yield p

运行时间现在减少到6000。