Лучшее параллельное простое число сито в го

Question

Посмотрев на код сита простого числа и увидев, как параллельная структура работ, я считаю, что это очень элегантно. Тем не менее, это также крайне неэффективно, и IIRC, эквивалентный O (n ^ 2) операция проверки делимости числа m на разделив его на каждое число меньше, чем m. Я полагаю, что я мог бы вместо измените его, чтобы использовать операцию O (n ^ 1.5) проверки делимости м путем деления его на каждое число, меньшее или равное sqrt (м). Однако оказалось, что это оказалось намного сложнее, чем я ожидал.

Я знаю, что это больше вопрос алгоритмики, но это также один чрезвычайно актуально для параллелизма. Как бы реализовать O (n ^ 1.5) версия алгоритма?

Answer 1

Одно место для поиска - stackoverflow , например, вопрос Concurrent Prime Generator . Среди ответов один, который использует Go и каналы .

Answer 2

Сито Эратосфена идентифицирует простое число p_i на итерации i и удаляет все кратные числа p_i из рассмотрения в последовательных итерациях. Учитывая это, единственное, что вы можете здесь распараллелить, это операция обрезки. Это может быть ускорено только постоянным фактором, так что вы не измените алгоритма таким образом.

Answer 3

Элегантные, но неэффективные реализации первичного сита уже хорошо известны сообществу функционального программирования. Эта бумага Мелиссы О'Нил дает хороший обзор ленивых "потоковых" первичных сит, а также представляет эффективные альтернативы. (Он использует Haskell, но все равно должен быть хорошо прочитан)