Есть ли библиотека Python для перечисления простых чисел?

Question

Есть ли библиотека Python для перечисления простых чисел?

Существует ли библиотечная функция, которая может перечислять простые числа (в последовательности) в Python?

Я нашел этот вопрос Самый быстрый способ перечислить все простые числа ниже N, но я предпочел бы использовать чью-то надежную библиотеку, чем свернуть свою собственную. Я был бы счастлив сделать import math; for n in math.primes:

1062 4

python

4 ответов:

Comments

Ничего не найдено.

casevh · Accepted Answer · 2012-11-11 05:09:27

Библиотека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.

SparkAndShine · Accepted Answer · 2017-02-24 15:38:21

SymPy - это еще один выбор. Это библиотека Python для символьной математики. Он предоставляет несколько функций для prime.

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]

Colonel Panic · Accepted Answer · 2015-11-10 11:54:38

Задав этот вопрос, я написал оболочку Python вокруг библиотеки C++ primesieve. 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

Arion · Accepted Answer · 2017-05-23 13:30:59

Не существует алгоритма постоянного времени для генерации следующего простого числа; именно поэтому большинство библиотек требуют верхней границы. На самом деле это огромная проблема, которую необходимо решить для цифровой криптографии. RSA выбирает достаточно большие простые числа, выбирая случайное число и проверяя его на примитивность, пока не найдет простое число.

Учитывая произвольное целое число N, единственный способ найти следующее простое число после N состоит в том, чтобы пройти через N+1 до неизвестного простого числа P. простота.

Тестирование на примитивность очень дешево, и есть библиотеки python, которые делают это: алгоритм простых чисел AKS в 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 и т. д..