问题标签 [sieve-of-eratosthenes]

我已经用 C++ 编写了一个 Eratosthenes 算法的筛子，它适用于我测试过的较小的数字。但是，当我使用大数字，即 2 000 000 作为上限时，程序开始给出错误的答案。谁能澄清为什么？

感谢您的帮助。

编辑：我刚刚进行了一些调试，发现它可以在 400 左右的限制下工作。但是，在 500 时，它关闭了 - 它应该是 21536，但是是 21499

编辑2：啊，我发现了两个错误，这些似乎已经解决了问题。

第一个是由其他回答的人发现的，并且 n 溢出 - 在被设为 long long 数据类型后，它已经开始工作。

第二个相当值得大惊小怪的错误是 r 中的布尔值必须被初始化。在检查素数以使它们全部为假之前运行循环之后，得到正确的答案。有谁知道为什么会这样？

I am stuck on trying to get the sieve to work. When I debug it, it tells me that stuff like 9 and 15 still evaluate to true when they go through the sieve. What causes this? Also, am I using the vector properly to get the highest prime factor?

我正在尝试创建一个多线程的埃拉托色尼筛

线程数默认设置为 4，但用户可以将它们指定为命令行参数。

我试图用几个不同的线程同时标记数组中素数的所有间隔。因此，包含 0 或 1 的数组被拆分为 arrayElements/threadNumber。

每个线程都有一个指定的数组的起始位置和结束位置，以便它检查其中的素数间隔。

因此，例如让我们假设您想要达到的数字是 20，并且您有 4 个线程。线程 0 将从 0 开始并上升到 20/4-1。下一个将从 20/4*threadNumber 开始，一直到 (20/4*nextThreadNumber)-1，依此类推。

然后我必须检查找到的素数是否在其中一个线程的数组区域内。这是因为如果是，则该素数不能被标记为非素数。我遇到了一个问题，因为素数在超出第一个线程的范围后会被标记为非素数，因为素数会自行相除。

正如您在下面看到的，我发现startingPosition 是否可以被素数整除。如果是，我将其设置为该线程的“非素数搜索”起点，并从那里增加素数，将范围内的每个实例标记为非素数。如果不是，那么我计算下一个非素数是什么（基于素数）并将其作为开始。

在这一切结束时，这是您通常的“以素数为间隔循环遍历数组，将每个实例标记为非素数”。

长话短说，我必须让这个数字达到 32 位整数（大约 20 亿）的范围。它适用于较小的数字，但在对 140 万个数字进行一些基准测试后，它需要 13.4 秒。540 万只需要 37.3 秒。1000 万只需要 68 秒。对于 20 亿，它只是继续工作（我让它运行了 10 分钟或更长时间），看不到尽头。

那么，我该如何改进我的代码呢？是什么导致它需要这么长时间？它似乎并不比单线程实现快（我将线程参数设置为 1 表示单线程，1000 万个数字需要 56 秒）

所以，这里是代码，与

定义 maxNum 10483646

线程函数：

现在主函数拥有算法的其余部分并创建线程：

我提前感谢大家的耐心和帮助！

编辑：我必须使用 pthreads

编辑 2：我以How to sleep or pause a PThread in c on Linux作为示例来尝试指导一些条件锁定和解锁。因为我确实想暂停和取消暂停素数的标记。我将 while 语句（使用 lock 和 unlock 语句）作为一个组放在我的线程函数中，在其中发现了 start/stop 部分。当在具有锁定/解锁语句的算法的内部 if 语句中找到素数时，我将 int 的标记设置为 1，并在具有锁定/解锁语句的 if 语句之外将该变量设置为 0。

那是我应该做的吗？

我正在编写一个多线程的 Eratosthenes 筛，我必须使用 pthreads。我很确定这样做的方法是使用互斥锁和 cond_waits。我在程序开始时创建了 4 个线程，然后我必须强制它们等待，直到 Eratosthenes 的筛子找到一个素数。然后我必须解除阻塞线程，以便它们可以标记位数组中该素数的每次迭代。然后，他们必须再次阻塞并等待下一个素数，直到埃拉托色尼筛算法耗尽自己的新数字。

这是我的线程函数的代码：

doneFlag 是我在埃拉托色尼筛算法完成所有数字时设置为 1 的标志。我希望带有 cond_wait() 函数的 while 循环会导致线程等待输入（只要还有输入要给出）

这是 main() 函数中的 Sieve 部分：

不知何故，复合数字没有被标记为复合数字（尽管有几个是）。我假设因为它与 main() 函数的竞争条件有关，它如何在线程仍在后台运行时不断找到更多素数，从而在线程仍在工作时更改素数。

我怎样才能解决这个问题？我的 locks/cond_wait 设置正确吗？我很难在网上找到这方面的资源。

谢谢！

编辑：我还想确保我的每个线程都可以同时运行该函数（该函数将数组中的元素标记为复合元素）。也许互斥锁在我的线程函数中不是一个好主意，因为我希望它们一起运行？（每个线程占用数组的不同段）

我有一个需要使用数组的任务的问题。我需要创建埃拉托色尼筛算法并打印出所有素数。我很困惑，因为据我所知，我的操作顺序是正确的。这是代码：

我首先将数组中的所有数字设置为 true。然后第二个循环将从 2 开始“x”，然后在它内部是一个嵌套循环，它将“x”乘以“n”的值，并且“n”将继续增加，只要该乘积的乘积（“y ") 低于 1000。一旦 "y" 达到最大值，"x" 将上升一个数字并重复该过程，直到所有非质数都设置为 false。

这是我编写代码时的逻辑，但是当我尝试运行它时，我得到了“ArrayIndexOutOfBoundsException”错误。据我所知，我将所有内容都设置为低于 1000，因此它不应该超过数组大小。

我知道它可能不是最有效的算法，因为随着“x”的增加，它会超过已经超过的数字，但它是我能想到的最简单的算法。

我正在尝试初始化一个整数数组并将所有元素设置为 1。我需要该数组的上限为 4294967295，或 32 位可能的最大数量unsigned int。

这对我来说似乎是一项微不足道的任务，应该是，但我遇到了segfault. 我可以for空循环运行它，它似乎工作正常（虽然速度很慢，但它正在处理近 43 亿个数字，所以我不会抱怨）。当我尝试在循环中执行任何类型的操作时，问题似乎出现了。我在下面的指令 - primeArray[i] = 1;- 导致segfault错误。据我所知，这不应该导致我超出数组。如果我注释掉那一行，没有segfault。

已经很晚了，我疲惫的眼睛可能只是错过了一些简单的东西，但我可以用另一副。

这是我所拥有的：

我一直在尝试用 JavaScript 编写Sieve of Eratosthenes算法。基本上我只是按照以下步骤操作：

1. 创建一个从 2 到 (n-1) 的连续整数列表
2. 让第一个素数 p 等于 2
3. 从 p 开始，以 p 为增量向上计数并删除这些数字中的每一个（p 和 p 的倍数）
4. 转到列表中的下一个数字并重复 2,3,4
5. 将无意删除的素数添加回列表

这就是我想出的：

它适用于小数字，但不适用于大于一百万的数字。我使用 Node.js 进行测试，这个过程似乎无穷无尽，没有出现内存错误。我在这里阅读了一个解决方案（也在 javascript 中），但仍然无法完全理解它。

问题：如何使这项工作适用于足够大的数字，例如一百万及以上？

我是 CUDA 的新手。为了弄脏我的手，我试着写了一个埃拉托色尼筛法（用于找出不超过某个数 n 的所有素数）。

我必须做很多事情才能让它工作，这似乎是不必要的。我很好奇是否有人知道更自然（并且仍然是 CUDA 优化）的方法。

1. 要在 isPrime 数组中获取标记为素数的条目，我必须进行两次单独的内核调用。第一个计算每个线程块中素数的数量，并将该块中小于 i 的素数分配给每个条目 i。然后我必须再次调用以添加所有先前块中的素数，以获得最终索引。
2. 但更糟糕的是，因为为了避免大量并发读取，我不得不将块中素数的数量存储在每个 THREADS_PER_BLOCK 索引处的单独数组中，从而有效地使算法所需的内存加倍。似乎应该有一种方法让所有线程为每个块读取相同的值，而不必复制它很多次。
3. 尽管如此，clearMultiples 方法中仍然存在并发读取的问题。尤其是对于像 2 和 3 这样的小素数，每个线程都必须读取其中的值。难道没有办法处理这个问题吗？

谁能看看我的代码并告诉我是否有什么明显可以做的更简单或更高效的事情？

我在做什么特别低效（除了在课程结束时打印出所有素数）？

每次内核调用后是否需要调用同步？

我还需要在 memcpy 之后进行同步吗？

最后，为什么当我将 THREADS_PER_BLOCK 设置为 512 时它不起作用？

谢谢

我试图对埃拉托色尼筛法给出更精确的近似值。

我使用的基本操作和权重：

我的证明：

我的证明正确吗？我在文献中发现复杂度是 O(nlog(log(n))) 或 O(nlog(log(n))/log(n))。