java - Eratosthenes算法的并行筛寻找素数

Question

埃拉托色尼筛法的两种并行化

1. 使用 Java 和
2. 将 C/C++ 与 Pthread 结合使用

找到 2 核和 4 核 CPU 的最佳阈值。

谁能帮我看看怎么做。我正在学习 Java 和 C/C++ 的线程。我需要什么来并行化这个算法

Answer 1

请注意，使用 Sieve of Eratostheens查找素数表的方法，一旦找到素数i - 你设置i*n作为每个n的非素数.

请注意，对于您知道的 2 个元素，它们是质数 - i,j你可以并行进行，i不需要来自 j 的任何信息反之亦然。
对于每k个素数当然也是一样。

但是请注意，判断一个数是否为素数 - 取决于最后的计算!因此，一个 barrier在将数字标记为非素数和找到下一个要使用的素数之间需要。

一个好的起点可以是:

repeat until finished filling the table:
    1. Find k prime numbers [serially]
    2. Fill the table for these k numbers [parallely]
    3. after all threads finished step 2 [barrier] - return to 1

既然是作业，我就只提示这些，剩下的交给你。如果您以后有任何具体问题 - 提出一个新问题并向我们展示您已经做过的事情。

编辑:一个更重要的提示，注意如果i是素数，计算从i导出的所有非素数不会影响 j 的事实是每个 i < j < 2i 的素数.使用这个事实找到 k质数，例如，您不希望在算法的第一次迭代中将 2、3、4 作为质数。