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

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

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

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

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

Где взять?

На гитхабе:

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

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

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

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

На данный момент реализован достаточно примитивный алгоритм проверки очередного числа 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).

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

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

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

Автор: Dair_Targ