是否有Python中可以枚举素数(按顺序)的库函数?
我在这个问题Fastest way to list all primes below N找到了答案,但是我更愿意使用其他人可靠的库而不是自己编写。我很乐意做这样的事情:import math; for n in math.primes:
是否有Python中可以枚举素数(按顺序)的库函数?
我在这个问题Fastest way to list all primes below N找到了答案,但是我更愿意使用其他人可靠的库而不是自己编写。我很乐意做这样的事情:import math; for n in math.primes:
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]
isprime
的源代码,它只能确定地检查质数是否小于 2^64。 - Gallifreyannext_prime()
函数。这个简单的函数将创建一个生成器,提供无限的素数供应:import gmpy2
def primes():
n = 2
while True:
yield n
n = gmpy2.next_prime(n)
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
primes()
的启动时间,但对于重复调用来说速度会更快。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
我也需要这个东西,于是决定自己动手练习一下很多事情。
在这里: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'用于管理库及其设置。
我希望有人会发现它有用,我很高兴收到任何建议或错误报告。
https://pypi.org/project/primesieve/
相比SymPy非常快。我正在Win10上使用Python3。
没有常数时间算法可以生成下一个质数;这就是为什么大多数库需要一个上限。这实际上是数字加密需要解决的一个巨大问题。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等整除的数字。
import numpy
然后呢?http://docs.scipy.org/doc/numpy/search.html?q=prime - Colonel Panic