Модуль генерации простых чисел

Кто-то любит горы Кавказа, кто-то горы кокоса...

… а мне нравится решать задачи Project Euler ^[1]. Конечно, я не могу похвастаться 350+ решёнными задачами, но четвёртый уровень (100..125) набрал честно. И в процессе этого набора, как подобает разработчику обыкновенному, начал выносить повторяющиеся фрагменты в отдельный модуль.

Надо сказать, что, по моим ощущениям, не менее половины представленных задач так или иначе связано с простыми числами. Например, найти наименьшие 5 простых чисел, таких, что любая пара из них, записанная в любом порядке как одно число (34, 56 -> 3456) будет так же простым числом (60 ^[2]). Или найти 1<=n<=1000000, такое что n/phi ^[3](n) максимально (69 ^[4]).

На днях дошли руки, что бы рабочее месиво «лишь бы посчитать, да побыстрее» причесать и извлечь оттуда модуль генерации простых чисел. Зачем это надо? Кому-то пригодиться как ещё-один-модуль-на-питоне ^[5]. Кто-то может увидеть ещё один пример того, как писать не надо. А я, надеюсь, получу порцию тонизирующей критики и прочих советов.

Где взять?

На гитхабе:

git clone git://github.com/dair-targ/primegenerator.git

Пока есть только один модуль primes.py и тесты к нему.

Как с этим работать?

Примеры использования приведены в test_primes.py. Основная идея:

# pg() -- функция, возвращающая дефолтный генератор
from primes import pg

# Факторизация
assert pg().prime_factors(1234567890) == {2: 1, 3: 2, 5: 1, 3607: 1, 3803: 1}

# Итерация по всем простым числам, не превосходящим 10**6
for p in pg().iterator(10**6):
    print p

Помимо этого, есть методы разложения числа на простые (и не только) множители, рассчёт НОД и НОК, подсчёт количества делителей.

Как оно работает?

Модуль рассчитан прежде всего на работу с большим количеством простых чисел. То есть по скорости работы для одного большого простого числа он, конечно, будет сильно уступать тому же тесту Агравала—Каяла—Саксены ^[6]. Однако, для задач поиска всех простых чисел, не превосходящих заданное, реализованные алгоритмы оказываются достаточно эффективными.

На данный момент реализован достаточно примитивный алгоритм проверки очередного числа N на простоту — проверка на наличие простых делителей на промежутке [2, sqrt(N)] с шагом 2. Результаты работы:

$> rm /tmp/primes.cache # Удаления кэша -- второй раз простые числа вычислятся не будут.
$> time python -c 'from primes import pg; [p for p in pg().iterator(10**6)]' # Все простые числа до 1 миллиона.

real	7m2.104s
user	7m1.710s
sys	0m0.060s

Кроме этого, в модуле реализован эффективный алгоритм факторизации чисел:

$> rm /tmp/primes.cache
$> time python -c 'from primes import pg; print pg().prime_factors(123456789012345)' # Разложим это число на простые множители
{3: 1, 5: 1, 283: 1, 3851: 1, 7552031L: 1}

real	0m0.060s
user	0m0.044s
sys	0m0.012s

И, повторюсь, НОД и НОК на его основе.

Недостатки и планы

Недостатки:

• Плохая работа с файловой системой, написанная абы как;
• Thread unsafe;
• Недокументированный питоновский формат сохранения бинарных данных (python marshal ^[7]).

Ближайшие планы:

• Изменить формат сохранённых данных (что бы было возможно читать их из другой программы, например, на C);
• Добавить корректную работу с кэшом при удалении объекта и выходе.
• Добавить CLI-интерфейс для генерации файла с простыми числами, разложения чисел на множители и т.п.;
• Возможно, реализовать более быстрые алгоритмы поиска и проверки простых чисел.

Надеюсь, это поделие будет кому-нибудь интересно. Спасибо за внимание!

Автор: Dair_Targ