hadoop - 生成素数的并行算法（可能使用 Hadoop 的 map reduce）

Question

生成素数是我经常尝试的一个玩具问题，尤其是在尝试新的编程语言、平台或风格时。

我正在考虑尝试使用 Hadoop（Map Reduce）编写质数生成算法或质数测试算法。

我想我会发布这个问题来获取提示、参考、算法和方法。

虽然我的主要兴趣是基于 Map Reduce 的算法，但我不介意查看新的 Hadoop 编程模型或例如使用PiCloud

关于质数生成，我似乎有一些有趣的问题：here、here和here，但没有任何与 Parallel 方法相关的问题引起我的注意。

提前致谢。

Answer 1

这是一种基于映射和归约（折叠）的算法。它表达了埃拉托色尼的筛子

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

对于奇数素数（即没有 2）。折叠树无限向右加深，像这样：

其中每个素数标记该素数的奇数倍流，例如7 : 49, 49+14, 49+28, ... ，它们全部合并以获得所有合数，然后在合数之间的差距。它在 Haskell 中，所以时间由惰性求值机制隐式处理_{（以及算法调整，每个比较节点总是让左边的第一个数字通过而不要求右边的数字，因为它保证是反正更大）}。

可以使用奇数代替奇数作为生成倍数的种子，以简化事情（具有明显的性能影响）。

作品可以自然地划分为连续素数正方形之间的片段。Haskell 代码如下，但我们也可以将其视为可执行伪代码_{（其中:是列表节点惰性构造函数，f(x)编写了函数调用f x，括号仅用于分组）}：

primes = 2 : g []
  where
    g ps = 3 : minus [5,7..] (_U [[p*p, p*p+2*p..] | p <- g ps])
    _U ((x:xs):t) = x : union xs (_U (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 代码在生成器方面的近似翻译；这是Python 中的一个。