2

不久前我遇到了这个（非常）简单的程序。它只输出前 x 个素数。我很尴尬地问，有没有办法让它更“pythonic”，即在使其（更多）可读的同时压缩它？切换功能很好；我只对可读性感兴趣。

谢谢

from math import sqrt


def isprime(n):
  if n ==2:
    return True
  if n % 2 ==0 : # evens
    return False

  max = int(sqrt(n))+1 #only need to search up to sqrt n 
  i=3
  while i <= max: # range starts with 3 and for odd i
    if n % i == 0:
      return False
    i+=2

  return True



reqprimes = int(input('how many primes: '))
primessofar = 0
currentnumber = 2
while primessofar < reqprimes:

  result = isprime(currentnumber)

  if result:
     primessofar+=1
     print currentnumber
     #print '\n'

  currentnumber += 1
4

8 回答 8

7

您的算法本身可能以 Python 方式实现，但以功能方式重写算法通常很有用 - 您最终可能会得到一个完全不同但更具可读性的解决方案（这甚至更具 Python 风格）。

def primes(upper):
    n = 2; found = []
    while n < upper:
        # If a number is not divisble through all preceding primes, it's prime
        if all(n % div != 0 for div in found):
            yield n
            found.append( n )
        n += 1

用法：

for pr in primes(1000):
    print pr

或者，考虑到 Alasdair 的评论，一个更有效的版本：

from math import sqrt
from itertools import takewhile

def primes(upper):
    n = 2; foundPrimes = []
    while n < upper:
        sqrtN = int(sqrt(n))
        # If a number n is not divisble through all preceding primes up to sqrt(n), it's prime
        if all(n % div != 0 for div in takewhile(lambda div: div <= sqrtN, foundPrimes)):
            yield n
            foundPrimes.append(n)
        n += 1
于 2009-11-21T13:29:15.570 回答
6

给定的代码效率不高。替代解决方案（同样低效）：†

>>> from math import sqrt
>>> def is_prime(n):
...     return all(n % d for d in range(2, int(sqrt(n)) + 1))
... 
>>> def primes_up_to(n):
...     return filter(is_prime, range(2, n))
... 
>>> list(primes_up_to(20))
[2, 3, 5, 7, 11, 13, 17, 19]

此代码使用all、range、int、math.sqrt和filter。list它与您的代码并不完全相同，因为它打印了一定数量的素数，而不是n 个素数。为此，您可以这样做：

>>> from itertools import count, islice
>>> def n_primes(n):
...     return islice(filter(is_prime, count(2)), n)
... 
>>> list(n_primes(10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

这引入了另外两个函数，即itertools.count和itertools.islice。（最后一段代码仅在 Python 3.x 中有效；在 Python 2.x 中，使用itertools.ifilter代替filter.）

  †：更有效的方法是使用埃拉托色尼筛。

于 2009-11-21T13:29:11.420 回答
5

风格指南中的一些小事。

  • 使用四个空格，而不是两个。（我个人更喜欢标签，但这不是 Pythonic 的方式。）
  • 更少的空行。
  • 一致的空格：n ==2:=>n == 2:
  • 在变量名称中使用下划线：currentnumber=>current_number

    • 于 2009-11-21T13:26:26.370 回答
    2

    首先，您不应该将 max 分配给变量，因为它是用于从可迭代中找到最大值的内置函数。此外，整个代码部分可以写成

    for i in xrange(3, int(sqrt(n))+1, 2):
    if n%i==0: return False

    另外，不用定义一个新的变量 result 并将 isprime 返回的值放入其中，您可以直接执行

    if isprime(currentnumber):
    于 2009-11-21T13:39:23.460 回答
    2

    我最近在函数式 python 中找到了 Project Euler 解决方案，它有一些非常好的使用这样的素数的例子。7 号非常接近您的问题：

    def isprime(n):
    """Return True if n is a prime number"""
    if n < 3:
        return (n == 2)
    elif n % 2 == 0:
        return False
    elif any(((n % x) == 0) for x in xrange(3, int(sqrt(n))+1, 2)):
        return False
    return True

def primes(start=2):
    """Generate prime numbers from 'start'"""
    return ifilter(isprime, count(start))
    于 2009-11-21T14:48:10.840 回答
    1

    通常，您不会将 while 循环用于此类简单的事情。您宁愿创建一个范围对象并从那里获取元素。因此，您可以将第一个循环重写为此，例如：

    对于范围内的 i (3, int( sqrt( n ) ) + 1, 2 )：
    如果 n % i == 0：
        返回假

    如果你缓存你的素数并且在检查新数字时只检查以前的素数，那会好得多。您可以通过这种方式节省大量时间（并以这种方式轻松计算更大的素数）。n这是我之前编写的一些代码，可以轻松获取所有素数：

    def primeNumbers ( 结束 ):
    素数 = []
    素数.追加（2）

    对于范围内的 i (3, end, 2)：
        isPrime = 真

        对于素数中的 j：
            如果我 % j == 0：
                isPrime = 假
                休息

        如果是素数：
            素数.追加（我）

    返回素数

打印素数（20）
    于 2009-11-21T13:40:29.807 回答
    1

    您可以使用筛算法（所有素数都小于 100）使其更加 Pythonic：

    def primes(n):
    sieved = set()
    for i in range(2, n):
        if not(i in sieved):
            for j in range(i + i, n, i):
                sieved.add(j)
    return set(range(2, n)) - sieved

print primes(100)

    一个非常小的技巧将把它变成你的目标。

    于 2009-11-21T14:13:56.323 回答
    1

    翻译自stacktrace.it的聪明人（特别是 Daniele Varrazzo），这个版本利用二进制最小堆来解决这个问题：

    from heapq import heappush, heapreplace

def yield_primes():
    """Endless prime number generator."""

    # Yield 2, so we don't have to handle the empty heap special case
    yield 2

    # Heap of (non-prime, prime factor) tuples.
    todel = [ (4, 2) ]

    n = 3
    while True:
        if todel[0][0] != n:
            # This number is not on the head of the heap: prime!
            yield n
            heappush(todel, (n*n, n))   # add to heap

        else:
            # Not prime: add to heap
            while todel[0][0] == n:
                p = todel[0][1]
                heapreplace(todel, (n+p, p))
                # heapreplace pops the minimum value then pushes: 
                # heap size is unchanged

        n += 1

    这段代码不是我的，我也不完全理解（但解释在这里:)），所以我将此答案标记为社区 wiki。

    于 2009-11-21T14:24:47.407 回答