Как реализовать эффективный бесконечный генератор простых чисел в Python?
Это не домашняя работа, мне просто любопытно.
БОГ является ключевым словом здесь.
Я хочу использовать его как for p in primes(). Я полагаю, что это - встроенная функция в Haskell.
Так, ответ не может быть столь же наивным, как "Просто делают Решето".
В первую очередь, Вы не знаете, сколько последовательных начал будет использовано. Ну, предположите, что Вы могли придумать 100 из них за один раз. Вы использовали бы тот же подход Решета, а также частоту формулы простых чисел?
Я предпочитаю непараллельный подход.
Спасибо за чтение (и запись ;))!
4 ответа
Выполните сегментированное сито, где размер сегмента определяется доступной памятью или максимальным размером битового набора.
Для каждого сегмента представляют числа в некотором интервале [n; n + segment_size) как набор бит и решето со всеми простыми числами ниже квадратного корня из верхней границы.
Использование набора битов требует меньше памяти, чем хэш-таблица или древовидная структура данных, потому что вы работаете с плотными наборами чисел.
Это изначально не мой код, однако, его стоит отправить. Оригинал можно найти здесь: http://code.activestate.com/recipes/117119/
def gen_primes():
D = {}
q = 2 # first integer to test for primality.
while True:
if q not in D:
# not marked composite, must be prime
yield q
#first multiple of q not already marked
D[q * q] = [q]
else:
for p in D[q]:
D.setdefault(p + q, []).append(p)
# no longer need D[q], free memory
del D[q]
q += 1
Это генератор, так что используйте его как любой другой.
primes = gen_primes()
for p in primes:
print p
Для генерации и размещения в наборе, 1 миллион праймов, на моем рабочем столе требуется 1.62s.
Вот генератор, который немного более похож на то, как это сделано в Haskell: фильтрация против составов известных простых чисел с последующим добавлением оставшихся простых чисел в список.
def gen_primes():
primes = []
i = 2
while True:
prime = True
for p in primes:
if not (i % p):
prime = False
break
if prime:
yield i
primes.append(i)
i += 1
Несколько раз назад я написал статью о генераторе бесконечных простых чисел:
http://stacktrace.it/2008/ 01 / progetto-eulero-проблема-3 /
Это на итальянском, но у вас может быть неприятный перевод с помощью Google: http://tinyurl.com/yzpyeom