前一篇我们给出了筛法求素数的基本代码，但是针对比较大的数据量，运算速度难以接受。我们观察到运算资源并不饱和，浪费了CPU。简单的改进方式是变为并行计算，用多线程提高本机并行能力，如果以后有网络，还可以分布到不同机器节点上。
要做到并行计算，首先要分析算法中哪些环节可以并行，哪些步骤要顺序执行。回头看筛法的计算过程，主要工作包括两个：选择除数和用除数过滤数列。选择除数是从小到大顺序进行，不能并行，而用除数过滤数列则是各自独立，所以能够并行。
我们并行的方式来变换原来的算法。大致思路如下——

1. 生成待过滤的数列
2. 根据并行数目将数列均匀切分，得到若干子数列
3. 从小到大循环除数，对每一个除数
    3.1. 并行同时过滤上述多个子数列
    3.2. 过滤N的平方根后停止循环
4. 连接所有子数列，输出最后的结果

这么做有个问题，我们切分数列的目的是为了在过滤时充分利用并行能力，但是在若干次过滤后，子数列将陆续被过滤完毕，所以并行计算单元（线程、机器节点等）会逐渐无用，要避免这种情况，应该在每次遇到子数列过滤完毕的时候重新切分数列。
最后的代码应该是这样

执行结果：

1
2
3
4
5

$ ruby prime_benchmark.rb 
    user     system      total        real
    10000   0.050000    0.000000   0.050000 (  0.048889)
    100000  0.650000    0.000000   0.650000 (  0.649779)
    1000000 39.810000   0.050000  39.860000 ( 39.961506

在我的4核机器上改进很明显。

注意：之前的代码还有一个遗留问题，被过滤掉的数字其实不用再来做除数，而现在这个版本因为要重新切分数列，所以有机会减少这个浪费，这也是速度明显提升的原因