primes - Erathostenes 筛.. 找到范围内的素数。如何获得起点？

Question

**注意：这与大学作业有关。我只是要求一些正确方向的指导。

我有一个单线程解决方案来查找素数（作业是转换为多线程解决方案）。它目前说从要检查的数字列表开始。从第一个素数 2 开始。（对于 0...N）。

我希望能够将列表 (0...N) 划分为 (0...25)、(26...50)、(51...75) 和 (76...100) ）。

如果每个列表的起点是第一个素数。我如何找到它？我必须有一个单独的功能来获得它吗？

谢谢。

Answer 1

我认为您想要一个多线程实现。您不需要每个列表都以素数开头。（考虑到您要计算的内容，这实际上有点循环。）想想一组工人，每个工人都有一个列表。与其让每个工人单独工作，不如考虑广播当前要筛选的素数，并让每个工人离开并将其应用到该工人的列表中。等到每个工人报告该阶段完成，找到下一个素数，然后重复。

Answer 2

要添加多线程，我只需使用一个变量来跟踪筛子的数量，然后启动一个线程来删除这些数字的倍数。

int a = 2;
//run thread 1
while(sieve[a] == false)
    a++;
//run thread 2
//etc.

显然还有更多内容..但这是一般的想法。