有没有一个Python库可以列出质数？

Question

有没有一个Python库可以列出质数？

32

是否有Python中可以枚举素数（按顺序）的库函数？

我在这个问题Fastest way to list all primes below N找到了答案，但是我更愿意使用其他人可靠的库而不是自己编写。我很乐意做这样的事情：import math; for n in math.primes:

- Colonel Panic

5

你提供的问题中有一个链接到numpy库，其中包含一个素数函数... - Hunter McMillen

5

请问这是什么？import numpy 然后呢？http://docs.scipy.org/doc/numpy/search.html?q=prime - Colonel Panic

你总是需要设定一个上限N...而对于较大的N值，可能需要很长时间... - Joran Beasley

这可能是你正在寻找的：https://dev59.com/6XRB5IYBdhLWcg3wn4fc ... 查看第一个答案（实际上链接到http://code.activestate.com/recipes/117119/） - Joran Beasley

1

为了后人的利益：@HunterMcMillen在2012年11月10日的评论完全是错误的 - numpy并没有提供一个素数函数。 - undefined

6个回答

18

gmpy2库有一个next_prime()函数。这个简单的函数将创建一个生成器，提供无限的素数供应：

import gmpy2

def primes():
    n = 2
    while True:
        yield n
        n = gmpy2.next_prime(n)

如果你会反复搜索素数，创建并重复使用一个在合理范围内的所有素数表（比如1,000,000以下）将会更快。这里是另一个使用gmpy2和埃拉托斯特尼筛法创建素数表的例子。`primes2()`首先从表中返回素数，然后使用`next_prime()`。

import gmpy2

def primes2(table=None):

    def sieve(limit):
        sieve_limit = gmpy2.isqrt(limit) + 1
        limit += 1
        bitmap = gmpy2.xmpz(3)
        bitmap[4 : limit : 2] = -1
        for p in bitmap.iter_clear(3, sieve_limit):
            bitmap[p*p : limit : p+p] = -1
        return bitmap

    table_limit=1000000
    if table is None:
        table = sieve(table_limit)

    for n in table.iter_clear(2, table_limit):
        yield n

    n = table_limit
    while True:
        n = gmpy2.next_prime(n)
        yield n

你可以根据需要调整table_limit。较大的值将需要更多的内存，并增加首次调用primes()的启动时间，但对于重复调用来说速度会更快。

免责声明：我是gmpy2的维护者。

- casevh

5

gmpy2的文档中写道：“next_prime(x)返回比x大的下一个可能的质数”。加粗部分是原文。我认为这需要进一步澄清。 - Dave Rove

9

自从我问了这个问题，我已经写了一个Python包装器来调用C++库primesieve，后来被primesieve维护者采纳。https://github.com/kimwalisch/primesieve-python 从PyPi安装https://pypi.org/project/primesieve/ pip install primesieve

>>> from primesieve import *

# Generate a list of the primes below 40
>>> generate_primes(40)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

# Generate a list of the primes between 100 and 120
>>> generate_primes(100, 120)
[101, 103, 107, 109, 113]

# Generate a list of the first 10 primes
>>> generate_n_primes(10)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

# Generate a list of the first 10 starting at 1000
>>> generate_n_primes(10, 1000)
[1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061]

# Get the 10th prime
>>> nth_prime(10)
29

# Count the primes below 10**9
>>> count_primes(10**9)
50847534

- Colonel Panic

2

我也需要这个东西，于是决定自己动手练习一下很多事情。

在这里：primes.py

警告：我尽可能修复了它的漏洞并对每个部分进行了检查，但我仍然是一个业余爱好者，所以我不保证高级或专业检查和无错误。使用需谨慎。

它会根据需要动态筛选质数，并以压缩的二进制格式存储和检索它们。

最有用的类是'primes'。这个类本身可以用作生成器、容器、下标和切片。

警告：小心迭代无限序列！

from primes import primes

for p in primes:  # 2, 3, 5, 7, 11, ...
    pass
primes[0]  # 2
primes[4]  # 11
primes[1:6:2] # primes object, generates 3, 7, 13
7 in primes  # True
8 in primes  # False

'

primes还有一些有用的方法：

'

primes.estimate(1000)  # 7830, real 1000th prime is 7927
primes.check(7)  # True
primes.index_of(11)  # 4 <- primes[4] = 11
primes.count_upto(10) # 4 <- len([2,3,5,7])
primes.sieve(5, 10)  # [5, 7] 
primes.in_range(5, 20, 2)  # primes object, generates 5, 11, 13, 19
primes.factor(12)  # {2:2, 3:1} <- 12 = 2^2 * 3^1
primes.phi(6)  # 6 <- Euler phi function,  number of smaller co-primes

质数对象本身是生成器、容器、可下标和可切片的，但仅限于质数子列表：

primerange1 = primes(1, None, 2)  # generator
for p in primerange1:  # 3, 7, 13, 19, ...
    pass
primerange1[1]  # 7
primerange1[:4:-1]  # generator: 13, 7, 3
2 in primerange1  # False

primerange2 = primes(6, 0, -2)  # generates 13, 7, 3
len(primerange2)  # 3
reversed(primerange2)  # primes object, generates 3, 7, 13

类'plib'用于管理库及其设置。

我希望有人会发现它有用，我很高兴收到任何建议或错误报告。

- Carsaxy

0

https://pypi.org/project/primesieve/

相比SymPy非常快。我正在Win10上使用Python3。

- Radim Cernej

这个答案已经在这里提供了：https://dev59.com/hWYr5IYBdhLWcg3w4t7m#33627223。当回答那些已经有答案的老问题时，请确保您提供的是一个新颖的解决方案或者比现有答案更好的解释。 - Mark Rotteveel

-1

没有常数时间算法可以生成下一个质数；这就是为什么大多数库需要一个上限。这实际上是数字加密需要解决的一个巨大问题。RSA通过选择随机数并测试素性直到找到一个质数来选择足够大的质数。

给定任意整数N，找到N之后的下一个质数的唯一方法是迭代N+1到未知质数P并测试其素性。

测试素性非常便宜，有Python库可以做到这一点：AKS Primes algorithm in Python

给定一个函数test_prime，那么无限质数迭代器将看起来像：

class IterPrimes(object):
    def __init__(self,n=1):
        self.n=n

    def __iter__(self):
        return self

    def next(self):
        n = self.n
        while not test_prime(n):
            n += 1
        self.n = n+1
        return n

有很多启发式方法可以用来加速这个过程。例如，跳过偶数或可被2、3、5、7、11、13等整除的数字。

- Arion

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- SparkAndShine · Accepted Answer

SymPy是另一个选择。它是用于符号数学的Python库。它提供了几个素数函数。

isprime(n)              # Test if n is a prime number (True) or not (False).

primerange(a, b)        # Generate a list of all prime numbers in the range [a, b).
randprime(a, b)         # Return a random prime number in the range [a, b).
primepi(n)              # Return the number of prime numbers less than or equal to n.

prime(nth)              # Return the nth prime, with the primes indexed as prime(1) = 2. The nth prime is approximately n*log(n) and can never be larger than 2**n.
prevprime(n, ith=1)     # Return the largest prime smaller than n
nextprime(n)            # Return the ith prime greater than n

sieve.primerange(a, b)  # Generate all prime numbers in the range [a, b), implemented as a dynamically growing sieve of Eratosthenes.

以下是一些例子。

>>> import sympy
>>> 
>>> sympy.isprime(5)
True
>>> list(sympy.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> sympy.randprime(0, 100)
83
>>> sympy.randprime(0, 100)
41
>>> sympy.prime(3)
5
>>> sympy.prevprime(50)
47
>>> sympy.nextprime(50)
53
>>> list(sympy.sieve.primerange(0, 100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]