通过线程获取素数。如何划分间隔？

Question

我想获得区间[min, max]中的所有素数。我想在n服务器上做微积分。将另一个n间隔中的初始间隔分开，以便在所有n服务器中管理大致相同的负载的最佳方法是？

---

[可选]

---

我有一个想法，但它没有工作，因为我的预期。我假设所有的数字都是素数，所以i的代码成本是i，验证的指令是素数。

如果我们记住这个方法：

然后，指令数来获得质数在区间[1100]为1+2+..+99+100 = 100(1+100)/2 = 5050。现在，如果我想在2个服务器（n=2）中执行这个微积分，我必须将这个负载分配给每个（每个指令2525条指令）。我想要的时间间隔由2525 = x(1+x)/2 -> x=71定义。

一般而言，通式为Load = (Interval(x) - Interval(x-1) + 1) * (Interval(x-1) + Interval(x))/2，即Load = (max - min + 1) * (min + max)/(2 * n)。

这样做，与x and y = [1:9999999]和n = 16，我有这样的结果：

http://s2.subirimagenes.com/imagen/previo/thump_948211012c6a4f9423d5b03819d.png

我不明白在所有服务器的同一时间和说明，是什么意思，这不是来划分间隔的方式。

任何想法？

Answer 1

我想你在寻找一种平行的方法。 这是work stealing算法的设计目的，也叫做Fork Join Pool。事实上，素数计算是盗窃工作的经典用例，因为告知n是否为素数需要迭代到sqrt(n)，所以越大越需要更长的时间。因此，平均分配给你的员工并等待每个员工完成其工作是不公平的，第一个核心将快速确定n是否为质数，并且处于空闲状态，另一个核心将继续忙于计算更大的数字。由于盗取闲置处理器的工作将从其邻居队列中窃取工作。

This implementation might be useful.

Answer 2

我解决了这个问题。我没有对我的时间间隔进行第一次完整的划分，并将每个部分分配给不同的服务器。我决定把间隔分成很小的部分（例如[min, max]/length^2），每个微积分服务器都有这些部分之一。当他们完成时，他们会得到另一个，直到没有更多的小时间间隔来计算。

我为什么要这样做？这是因为我无法确保我所使用的服务器具有相同的演算速度。