Питон генератор простых чисел

Основной генератор простых чисел в Python

Просто нужна была обратная связь с генератором простых чисел. например это нормально, он использует много ресурсов и т.д. Он не использует библиотеки, он довольно прост, и это отражает мое текущее состояние навыков программирования, поэтому не сдерживайтесь, как я хочу узнать.

def prime_gen(n): primes = [2] a = 2 while a < n: counter = 0 for i in primes: if a % i == 0: counter += 1 if counter == 0: primes.append(a) else: counter = 0 a = a + 1 print primes 

Особенно реализация Sieve of Erastothenes в принятом ответе ( stackoverflow.com/a/568618/3646530 ). Это связано с использованием генераторов. Вы можете получить больше информации о том, что такое генератор здесь: stackoverflow.com/a/231855/3646530

Вы можете использовать алгоритм генератора вместо возврата списка. Вы бы сохранили память таким образом. Также предпочтительным алгоритмом для генерации простых чисел, меньших числа, является сито Эрастотен.

5 ответов

Существует несколько оптимизаций:

def prime(x): if x in [0, 1]: return False if x == 2: return True for n in xrange(3, int(x ** 0.5 + 1)): if x % n == 0: return False return True 

Приведенный выше пример не генерирует простые числа, но проверяет их. Вы можете адаптировать те же самые оптимизации к вашему коду:)

Один из наиболее эффективных алгоритмов, найденных на Python, можно найти в следующем ответе на вопрос (используя сито):

Моя собственная адаптация ситового алгоритма:

from itertools import islice def primes(): if hasattr(primes, "D"): D = primes.D else: primes.D = D = <> def sieve(): q = 2 while True: if q not in D: yield q D[q * q] = [q] else: for p in D[q]: D.setdefault(p + q, []).append(p) del D[q] q += 1 return sieve() print list(islice(primes(), 0, 1000000)) 

На моем оборудовании я могу быстро сгенерировать первые миллионы простых чисел (учитывая, что это написано на Python):

[email protected] Thu Apr 23 12:58:37 ~/work/euler $ time python foo.py > primes.txt real 0m19.664s user 0m19.453s sys 0m0.241s [email protected] Thu Apr 23 12:59:01 ~/work/euler $ du -h primes.txt 8.9M primes.txt 

для теста лучше проверить 2 явно, а затем выполнить итерацию по xrange(3, int(x ** 0.5 + 1), 2) . Нет смысла проверять все четные числа.

Источник

Криптография и генерация больших однозначно простых чисел — критерий Поклингтона

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

О применении простых чисел в криптографии и не только можно прочитать здесь, а в данной статье сконцентрируемся на самом алгоритме.

Подходы к генерации простых чисел

И так пусть у нас есть заданное число порядка больше , и мы хотим получить простое число .

1. Для начала мы можем воспользоваться одним из решето-алгоритмов для получения всех простых чисел до заданного - Эратосфена, Аткина, Сундарама;
2. Второй подход это генерация рандомных нечётных чисел больше и проверка каждого из них на простоту через перебор делителей, вероятностные и истинные тесты простоты - подходы можно глянуть здесь;
3. Наконец третий подход это комбинирование элементов из подходов выше для создания более комплексных алгоритмов;

Описание алгоритма

Рассмотрим алгоритм из 3 подхода, который комбинирует решето Эратосфена для получения первичных простых чисел и критерий Поклингтона, который в свою очередь использует малую теорему Ферма, для получения однозначно простого числа. Как было сказано выше, алгоритм итеративный, то есть мы получаем большее простое из текущего .

1. Строим решето Эратосфена до , где это некая константа - например . Выбираем стартовое простое число - либо принимаем аргументом, либо из построенного решета. Переходим к шагу 2.
2. Имеем простое число - если , то результат алгоритма это , иначе мы хотим найти простое число - переходим к шагу 3.
3. Выбираем рандомно чётное числои запишем кандидат на простоту . Переходим к шагу 4.
4. Проверяем на делимость с простыми числами низкого порядка, полученными на шаге 1 - если число делится на одно из них, то оно составное и возвращаемся к выбору нового кандидата , то есть шагу 2. Иначе число может быть простым, поэтому переходим к шагу 5.
5. Выбираем рандомно число и проверяем для нашего кандидата на простоту исполнимость следующих двух условий и . Если оба исполняются, то по критерию Поклингтона число простое - заменяем и переходим к следующей итерации по поиску большего числа, то есть шагу 2. Иначе если не исполняется первое условие - , то по малой теореме Ферма число не является простым, поэтому переходим к выбору нового кандидата, то есть шагу 3. Иначе если не исполняется вторая часть, то анализ немного сложнее - мы нашли делитель для кандидата , поскольку. Предположим, что , что подразумевает не примитивный делитель, а значит не простое - переходим к повторному выбору, то есть шагу 3. Остаётся случай, когда , что означает , а решений этой конгруэнции существует не больше . Одно из решений это , поэтому на интервале существует не болеерешений, следовательно при действительно простом мы найдём (с вероятностью ) такое , которое бы удовлетворяло критерию Поклингтона, поэтому переходим к шагу 5 для повтора выбора .

Корректность алгоритма

Можно заметить, что полученное на каждой итерации простое число будет не меньше квадрата предыдущего, то есть иметь в два раза больше цифр - выполняя шаги описанные выше мы дойдём к простому числу больше . Из этого так же следует, что количество цифр в результирующем простом числезависит от выбора начального простого числа для алгоритма, поэтому если мы хотим сделать порядка , то это нужно учесть.

Исследование корректности и эффективности данного алгоритма выходит за пределы этой статьи, однако алгоритм имеет место быть из-за исследований Дирихле о простых числах в арифметических прогрессиях, исследований Люстерника о первом простом числе в такой прогрессии и гипотезы Крамера о расстояниях между двумя последовательными простыми числами.

Код алгоритма на Python

def generatePrime(n : int, primes = None, s = None): """Generates prime number with at least n digits: : param n: number of 10-based digits in the generate prime is at least n; : param primes: an iterable object of numbers that are used as small factors for pre-prime verification. If None, is computed using getSieve(1000); : param s: initial prime number - if None, last from primes is used; """ # Any prime number higher than the up_limit suffices the result. up_limit = 10**n # Get the list of small primes which are used as small divisors # to reject the n candidate before the Pocklington test. if not primes: primes = getSieve(1000) if not s: s = primes[-1] # initial prime while s < up_limit: lo, hi = (s + 1) >> 1, (s 

1) P1 = 222479360228659844149346639882089160021, D1 = 39 2) P2 = 327235960958148645696052834806967763219, D2 = 39 3) P3 = 1703805325300022851813841485118972214405495022945891, D3 = 52 4) P4 = 848995467487101811203366361379372085728608261197707959, D4 = 54 5) P5 = 1041875824682281112078115198781702612619843793759431, D5 = 52

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19 *

2 3 * 5 * 7 * * * 11 * 13 * 15 * 17 * 19 *

2 3 * 5 * 7 * * * 11 * 13 * * * 17 * 19 *

def sieve(n): primes=[] temp_list = [0 for x in range(0,n)] i,j=2,2 while(i*j= n: i,j = i+1,2 for i in range(2,n): if temp_list[i] == 0: primes.append(i) return primes if __name__ == '__main__': n = int(input()) print sieve(n)

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

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20