Параллельные алгоритмы генерации простых чисел (возможно, с использованием карты Hadoop)

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

Я думал о попытке написать алгоритм Prime Generation Generation или Алгоритм тестирования первичного номера с использованием Hadoop (Уменьшение карты).

Я думал, что поставил бы этот вопрос, чтобы получить советы, ссылки, алгоритмы, подходы.

Хотя мой основной интерес - это алгоритм, основанный на Map Reduce, я бы не прочь взглянуть на новые модели программирования Hadoop или, например, на использование PiCloud

У меня есть некоторые интересные вопросы здесь о Prime Number Generation: здесь, здесь и здесь, но ничего, связанное с параллельным подходом, не попало в глаза.

Ответы

Ответ 1

Здесь алгоритм, который построен на сопоставлении и сокращении (складной). Он выражает сито Eratosthenes

P= {3,5,7,...}\ U {{p ² p ² + 2p, p ² + 4p,...} | p в P}

для нечетных простых чисел (т.е. без 2). Сгибание бесконечно углубляется вправо, например:

где каждое простое число обозначает поток нечетных кратных этого простого числа, например. для 7: 49, 49 + 14, 49 + 28,..., которые объединены для получения всех составных чисел, а затем штрихи найдены в промежутках между составными числами. Это в Haskell, поэтому время позаботится неявно с помощью ленивого механизма оценки _{(и алгоритмической настройки, где каждое сравнение node всегда пропускает первое число слева, не требуя номера справа, потому что в любом случае гарантированно будет больше).}

Коэффициенты могут использоваться вместо нечетных простых чисел в качестве семян для генерации мультипликаторов, чтобы упростить ситуацию (с очевидными последствиями для производительности).

Работу можно разделить на сегменты между квадратами последовательных простых чисел. Далее следует код Haskell, но мы также можем рассматривать его как исполняемый псевдокод _{(где : - это список node lazy constructor, вызов функции f(x) написан f x, а круглые скобки используются только для группировки )суб > :}

primes () = 2 : ([3,5..] `minus` unionAll [[p*p, p*p+2*p..] | p <- prs]) 
  where 
    prs = 3 : ([5,7..] `minus` unionAll [[p*p, p*p+2*p..] | p <- prs])
    unionAll ((x:xs):t) = x : union xs (unionAll (pairs t))
    pairs ((x:xs):ys:t) = (x : union xs ys) : pairs t

union (x:xs) (y:ys) = case compare x y of 
    LT -> x : union  xs (y:ys) 
    EQ -> x : union  xs    ys 
    GT -> y : union (x:xs) ys

minus (x:xs) (y:ys) = case compare x y of
    LT -> x : minus  xs (y:ys) 
    EQ ->     minus  xs    ys 
    GT ->     minus (x:xs) ys

Обсуждение здесь. Более сложное, ленивое планирование здесь. Также этот SO-ответ показывает приблизительный перевод (связанного) кода Haskell с точки зрения генераторов.