Có thư viện Python để liệt kê các số nguyên tố không?

Question

Có chức năng thư viện nào có thể liệt kê các số nguyên tố (theo thứ tự) bằng Python không?

Tôi tìm thấy câu hỏi này Fastest way to list all primes below N nhưng tôi muốn sử dụng thư viện đáng tin cậy của người khác hơn là cuộn của riêng tôi. Tôi rất sẵn lòng làm import math; for n in math.primes:

Answer 1

Thư viện gmpy2 có hàm next_prime(). Chức năng đơn giản này sẽ tạo ra một máy phát điện sẽ cung cấp một nguồn cung cấp vô hạn các số nguyên tố:

import gmpy2 

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

Nếu bạn sẽ được tìm kiếm thông qua các số nguyên tố lặp đi lặp lại, tạo ra và tái sử dụng một bảng của tất cả các số nguyên tố dưới đây một giới hạn hợp lý (nói 1.000.000) sẽ nhanh hơn. Dưới đây là một ví dụ khác sử dụng gmpy2 và Sieve of Eratosthenes để tạo ra một bảng các số nguyên tố. primes2() trả về số nguyên tố từ bảng đầu tiên và sau đó sử dụng 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 

Bạn có thể điều chỉnh table_limit cho phù hợp với nhu cầu của mình. Giá trị lớn hơn sẽ yêu cầu nhiều bộ nhớ hơn và tăng thời gian khởi động cho lần gọi đầu tiên của số nguyên tố() nhưng sẽ nhanh hơn đối với các cuộc gọi lặp lại.

Lưu ý: Tôi là người duy trì gmpy2.

Answer 2

Không có thuật toán thời gian không đổi để tạo số nguyên tố tiếp theo; đây là lý do tại sao hầu hết các thư viện yêu cầu một ràng buộc trên. Đây thực sự là một vấn đề lớn cần được giải quyết cho mật mã số. RSA chọn số nguyên tố đủ lớn bằng cách chọn một số ngẫu nhiên và kiểm tra tính nguyên thủy cho đến khi nó tìm thấy số nguyên tố.

Với một số nguyên tùy ý N, cách duy nhất để tìm ra thủ tiếp theo sau khi N là để lặp qua N+1 cho biết Thủ P thử nghiệm cho tính nguyên.

Testing cho tính nguyên là rất rẻ, và có python thư viện mà làm như vậy: AKS Primes algorithm in Python

Với một hàm test_prime, so với một số nguyên tố lặp vô hạn sẽ giống như thế:

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 

Có một nhiều chẩn đoán bạn có thể sử dụng để tăng tốc quá trình. Ví dụ: bỏ qua số chẵn hoặc số chia hết cho 2,3,5,7,11,13, v.v.

Answer 3

Kể từ khi đặt câu hỏi này, tôi đã viết một trình bao bọc Python quanh thư viện C++. https://github.com/hickford/primesieve-python

>>> 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 

Answer 4

SymPy là một lựa chọn khác. Nó là một thư viện Python cho toán học biểu tượng. Nó cung cấp một số chức năng cho thủ tướng.

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. 

Dưới đây là một số ví dụ.

>>> 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]