简单的双素寻星仪

import math
primes = []
def get_primes(lower, upper):
  for num in range(lower, upper):
    for i in range(2, num):
      if num % i == 0:
        break
    else:
      primes.append(num)
print get_primes(int(raw_input("Enter lower boundary")), int(raw_input("Enter upper boundary")))
print primes

for i in range(0, len(primes) - 1):
  if primes[i+1] - primes[i] == 2:
    print str(primes[i]), str(primes[i+1]) 

#1 楼

样式

称为PEP 8的Python代码样式指南建议使用4个空格的缩进。

更多功能

您可以将逻辑拆分为更小的易于理解，测试和优化的逻辑部分（稍后再介绍）。

例如：

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

def get_primes(lower, upper):
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)

避免使用全局函数

如果您使用函数get_primes而不是附加到全局变量，而是使用适当的返回值，则将更易于使用。

def get_primes(lower, upper):
    primes = []
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)
    return primes

primes = get_primes(5, 56)  # get_primes(500000, 560000)
print primes

（再次）更多功能

您可以添加函数get_twin_primes以返回...双素数。

if __name__ == "__main__":

在Python中，使用if __name__ == "__main__":将您的函数/类定义与实际使用它的代码分开是实用（传统）的。这样就可以通过导入实现代码的重用：这些函数/类可以在不触发所有计算的情况下被其他模块使用。

现在，整个代码如下所示： br />
更优美的循环

我强烈推荐内德·巴切德尔（Ned Batchelder）的精彩演讲，称为“像当地人一样循环”（以及他所做的任何其他演讲）。您将学到很多有关Python迭代的知识，并且基本上，每当您编写“ range（len（list））”时，都有一种更好的方法。

在您的情况下，您会发现各种遍历列表中连续项的方法如下：

import math

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

def get_primes(lower, upper):
    primes = []
    for num in range(lower, upper):
        if is_prime(num):
            primes.append(num)
    return primes

def get_twin_primes(primes):
    twins = []
    for i in range(0, len(primes) - 1):
        if primes[i+1] - primes[i] == 2:
            twins.append((primes[i], primes[i+1]))
    return twins

if __name__ == "__main__":
    primes = get_primes(5, 56)  # get_primes(500000, 560000)
    print primes
    for a, b in get_twin_primes(primes):
        print a, b

（在Python 2中，您可以使用itertools.izip而不是zip，但是如果您正在学习Python，则可以应该尝试直接使用Python 3）。

然后，可以使用列表推导轻松地重写此代码：

def get_twin_primes(primes):
    twins = []
    for p1, p2 in zip(primes, primes[1:]):
        if p2 - p1 == 2:
            twins.append((p1, p2))
    return twins

更多列表推导

还可以在get_primes中使用列表推导法：

def get_twin_primes(primes):
    return [(p1, p2) for p1, p2 in zip(primes, primes[1:]) if p2 - p1 == 2]

使用内置函数（和生成器表达式）

您的函数可以使用内置的all以更简洁的方式编写。

def get_primes(lower, upper):
    return [num for num in range(lower, upper) if is_prime(num)]

您可以轻松地将其理解为“数字是质数，所有除法运算的结果都是非零余数”。

就像您以前的逻辑一样，但是您正在重用已经存在的内置函数，它会教给您新的知识事情：）

现在，整个代码如下：

def is_prime(n):
    return all(n % i != 0 for i in range(2, n))

优化

简单但非常有效检查素数时的优化是使用以下事实：如果一个数字是复合的，那么对于任何一对因素，一个都小于或等于平方根，另一个大于或等于平方根，因此您不必无需检查大于您所考虑数字平方根的值。在那里，您可以编写类似以下内容的代码：

import math

def is_prime(n):
    return all(n % i != 0 for i in range(2, n))

def get_primes(lower, upper):
    return [num for num in range(lower, upper) if is_prime(num)]

def get_twin_primes(primes):
    return [(p1, p2) for p1, p2 in zip(primes, primes[1:]) if p2 - p1 == 2]

if __name__ == "__main__":
    primes = get_primes(5, 56)  # get_primes(500000, 560000)
    print primes
    for a, b in get_twin_primes(primes):
        print a, b

您可以做的另一种优化是使用step中range的get_primes参数仅对奇数进行迭代（并添加“ 2” ”（如果需要，请在开头）。

#2 楼

要继续从乔赛（Josay）的答案开始，有一种更好的方法来生成一个低于极限的素数。这是一个主要的筛子，其中最简单的是Eratosthenes筛子。

您甚至可以将其编写为Python生成器，例如：

def prime_sieve(limit):
    # Array denoting if the index is prime, initially assume all primes
    prime = [True] * limit
    # Set the starting conditions
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        # No number smaller than i marked i as a multiple of it
        if is_prime:
            yield i
            # Set all multiples of i as not prime, starting with i*i
            for n in xrange(i * i, limit, i):
                prime[n] = False

请注意，如果您使用的是Python 3.x，则需要用xrange替换range。

现在它是一个生成器，使用zip一次循环了两个，就像Josay所做的那样，有点浪费（我们需要两个生成器，每个生成器都保存了几乎相同的内部状态，因此占用了两倍的内存...），即使它们是列表是非常好的。只需将先前的状态保存在变量中就更容易了，就像这样：

def prime_pairs(lower, upper):
    # Initialize generator of primes up to upper
    primes = prime_sieve(upper)

    # Forward generator up to lower
    p1 = next(primes)
    while p1 < lower:
        p1 = next(primes)

    # Yield all twin primes
    for p2 in primes:
        if p2 - p1 == 2:
            yield p1, p2
        p1 = p2


if __name__ == "__main__":
    lower = int(raw_input("Enter lower limit: "))
    upper = int(raw_input("Enter upper limit: "))
    for pair in prime_pairs(lower, upper):
        print pair

在Python 3.x中用print pair替换print(pair)，用raw_input替换input。 >

当您需要大量的底料时，底料筛方法的优势显而易见。使用乔赛（Josay）定义的get_primes函数，例如：

In[23]: %timeit sum(get_primes(0, 100000))
1 loop, best of 3: 344 ms per loop

而原筛明显更快（大约25倍）：

In [24]: %timeit sum(prime_sieve(100000))
10 loops, best of 3: 13.9 ms per loop

手头的任务也更快（这完全由质数的生成决定）：

In [33]: %timeit get_twin_primes(get_primes(0, 100000))
1 loop, best of 3: 348 ms per loop

In [34]: %timeit list(prime_pairs(0, 100000))
100 loops, best of 3: 14.5 ms per loop

/>另一种情况是，您想要的素数都很大，但是您并不在乎较小的素数双胞胎。在这里Josay的方法胜出（因为生成器方法将始终遍历整个生成器，并将其转发到下限）：

In [74]: %timeit get_twin_primes(get_primes(99900, 100000))
1000 loops, best of 3: 450 µs per loop

In [75]: %timeit list(prime_pairs(99900, 100000))
100 loops, best of 3: 14.7 ms per loop

99900被选择为此处的下限，以便该范围实际上包含一个质子孪生。


并显示与您相比，Josay的方法已经有多出色，这里是您的代码（包装在一个简单的函数中，并替换了print和yield）：

def get_primes_op(lower, upper):
    primes = []
    for num in range(lower, upper):
        for i in range(2, num):
            if num % i == 0:
                break
        else:
            primes.append(num)
    return primes


def twin_primes(primes):
    for i in range(0, len(primes) - 1):
        if primes[i + 1] - primes[i] == 2:
            yield str(primes[i]), str(primes[i + 1])

In [54]: %timeit list(twin_primes(get_primes_op(0, 100000)))
1 loop, best of 3: 1min 38s per loop

In [77]: %timeit list(twin_primes(get_primes_op(99900, 100000)))
1 loop, best of 3: 252 ms per loop

从我的代码到Josay的代码，这是惊人的280倍的速度增长；对于使用大量素数的代码，这是我的代码的> 6500倍的速度增长；在我的代码中，Josay的速度是560倍，而速度却只有17倍。下限接近上限的情况，上限也很大。

因此，作为结论，选择适合该工作的工具。然后测试哪种工具实际上是满足您特定需求的合适工具。

如果您需要一长串的质数低于某个上限但下限较低（可能甚至为0），则可以使用素筛生成器是这样的方法。

如果需要带有任意上下限的素数列表，则实现显式is_prime函数会更快。