Parallel algorithms for generating prime numbers (possibly using a Hadoop card)

Question

Generating prime numbers is a toy problem that I often do from time to time, especially when experimenting with a new programming language, platform, or style.

I was thinking of trying to write a Prime Generation Generation algorithm or a Primary Number Test Algorithm using Hadoop (Map Reduction).

I thought I would raise this question to get tips, links, algorithms, approaches.

Although my main interest is a Map Reduce-based algorithm, I would not mind looking at new Hadoop programming models or, for example, using PiCloud

I have some interesting questions here about Prime Number Generation: here , here and here , but nothing related to the parallel approach got into my eyes.

Thanks in advance.

Answer 1

Here is an algorithm that is built on matching and abbreviation ( folding ). He expresses a sieve of Eratosthenes

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

for odd primes (i.e. without 2). Bending infinitely deepens to the right, for example:

where each prime number denotes a stream of odd multiples of this prime number, for example. for 7 : 49, 49 + 14, 49 + 28, ..., which are combined to get all the composite numbers, and then the strokes are found in the spaces between the composite numbers. This is in Haskell, so time will be taken care of implicitly using a lazy evaluation mechanism _{(and algorithmic tuning, where each node comparison always skips the first number on the left, without requiring a number on the right, because in any case there will be more guaranteed).}

Odds can be used instead of odd primes as seeds for generating multipliers to simplify things (with obvious performance implications).

The work can be divided into segments between the squares of consecutive primes. The Haskell code follows, but we can also consider it as an executable pseudo-code _{(where : is the list of node lazy constructor, the function call f(x) written by fx , and parentheses are used only for grouping) sub>:}

 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 xy 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 xy of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys 

The discussion is here . More complicated, lazy planning is here . Also, this SO answer shows an approximate translation of the (related) Haskell code in terms of generators.