求 2…n 的所有质数
前置知识：
一个数 n 如果不能被 2...n 的数除尽，那么 n 就是一个质数。 但是因为某些原因如果 n 不能被 2…根号 n 的数除尽就足以证明 n 是质数。 又因为某个定理质数只要不被 2...根号 n 之间的质数除尽就可证明其是质数。 如:13 需要证明其不会被 [2，3] 除尽就可知其是质数。 因为我们求的 n 会非常大。所以要用例子中的算法。这意味着要把求出的质数保存下来。
正题:n 非常大 20 的几十次方之类 给你两台计算机，如何做到在两台计算机上计算用的时间约等于使用一台的时间的一半。
注：主要问的是思路 如：如何分割两台计算机分别的计算范围，不涉及具体算法或技术。
共享一个已知质数表，然后两台电脑异步算吧。
比如 pc A 算 a，pc B 算 b。如果 a 或 b 是质数，存入共享质数表里，然后 move on。感觉是这么回事。具体实现的话还要有些根据已知质数表过滤肯定不是质数的新数的函数了。
可以参考这个帖子 http://ruby-china.org/search?q=%E7%B4%A0%E6%95%B0 我觉得楼主的思路可能和出题者不太一样， 如果用筛选法来考虑这个问题的话，可以轻松设计成 map reduce 的形式计算，n 台计算机所需时间也刚好是 1/n
#15 楼 @jjym 呵呵 见笑了，我之前只想了算法，而代码的操作效率都很低，这里同一个算法考虑效率后重写一次。你再看看～
def compute_primes n
primes = [2]
(3..n).each{|i|
limit = Math.sqrt(i).to_i
primes.each{|p|
break if i % p == 0
if p >= limit
primes << i
break
end
}
}
primes
end
t = Time.new
result = compute_primes 1000000
puts Time.new - t
#paranoyang 的
def prime(n)
primes = Array.new(n, true)
primes[0] = false
primes[1] = false
(2..n).to_a.each do |it|
if primes[it]
times = 2
while it * times <= n
primes[it*times] = false
times += 1
end
end
end
ans = []
primes.each_with_index{|v,i| ans << i if v}
ans
end
t2 = Time.new
result2 = prime 1000000
puts Time.new - t2
#验证结果
puts result == result2
最后结果
3.409089914
1.013814049
true
改为 1000 万时的结果：
62.907095532
10.959379423
true
最后是无聊的 100 000 000
1697.931828172
140.165174387
true
这里再说一下多台计算机的思路：
def prime(n)
primes = Array.new(n, true)
primes[0] = false
primes[1] = false
(2..n).to_a.each do |it|
if primes[it]
times = 2
while it * times <= n
primes[it*times] = false
times += 1
end
end
end
ans = []
primes.each_with_index{|v,i| ans << i if v}
ans
end
假设有 x 台计算机。
在 2..n 那个迭代中，把 times 的范围先求出来，也即 2..(n / it - 1)。再将这些数分成 x 个等分的 list，每台计算机对 list 中每个元素做*it运算，并返回该 list，返回的 x 个 list 合并后，将合并结果分发给 x 台计算机，每台计算机维护 primes 素数表的 n/x 位，将 list 中其管辖范围内的 primes 置为 false。这样计算量恰可分为 x 份。
http://ruby-china.org/topics/2582 这帖子里的 qinsine 给的算法http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 似乎可以提高效率很多，你注意那个算法的演示动画，可以设 2 3 5 7 ..sqrt(n) 为基数，然后分配给不同的机器进行那个算法计算，调度器维护一张 2..N 的 hash，另外，根据常识，除 2 以外的所有偶数和除五以外的所有个位为 5 的奇数都不会是素数，所以 2 和 5 两个可以省略掉，这样 3 和 7 交给其他机器计算即可，输出所有素数只需 nums.each_with_index {|n, i| p i unless 两种特殊情况 or n }即可 如果 n 无限大，并且 sqrt(n) 也无限大，可以考虑递归思想计算
举个例子：N=1000 4 台机器 则约定 2 3 5 7 为素数 调度器计算 sqrt(1000) 约等于 32，每台机器计算一个数字 汇总 可以得到 32 以内的素数 然后调度器再平均分配这些素数到 worker，计算然后汇总 就能得到 1000 以内的素数了 这里 worker 可以记录之前的计算结果，从而避免重复计算。 如果 sqrt(n) 依然很大，则不断开方，直到范围有限为止（<120 即可，原因看 wiki 的那个算法演示）
@jjym @tassandar 筛法和提问者阐述的算法本质一样的（话说这不是很传统的方法吗），不考虑调用栈的时间的话，应该是恰好同样时间的，按照所谓的“筛法”的话分布式或许好写一些
@paranoyang 筛法对每一个有相同因子的数给一个标记，那么每个数就会有自己的质因子那么多次操作，而 #1 提出的办法是对每一个数从前面的质数里的整除性来判别是否是质数，有何差别
@jasl @paranoyang N 的量级是 20 的几十次方，比如 20 的 20 次方是 104857600000000000000000000，使用筛选法，相当于要把这些个数字都存下来，不太现实。用磁盘存都要 104857600000000 T 的空间，这基本上是不可实现的。 我给出一个算法，大家看看是否可行：
- 假定现有的质数表为 a1, a2, a3, ai
- 则产生一个子任务，计算 ai 到 ai^2 的质数；
- 第 2 步中产生大于 ai 的下一个质数 ai+1 后，可以产生一个新的子任务 ai^2a(i+1)^2，可以分配给另外一台机器； 举例子： 现在已经产生了 2,3,7, 其中一个子任务是计算 8-49 的质数，计算时，很快发现 11 也是质数，更新质数表，又产生一个新的子任务 49-121，完全可以在另一个计算机计算，后来有发现 13 也是，可以产生 121-169 的子任务，也提交到另外一个计算机，随着这个过程继续，不断产生更多的子任务，但是这些子任务都是可以独立运行的，不过要按顺序来，这样可以认为整个过程是两台或多台机器并行执行，是一台机器的 1/2。
@bhuztez 大家的算法都差不多哇。。。你也是要存质数表的嘛~估计出题人没考虑这些，提一个大数可能仅仅是为了夸张从而过滤一些低效的方案，而且题目里并没有说明硬件条件。理想状态下，像采用 google 那样的分布式存储集群，存储这些数字本身是有可能的。