使用预计算素数的埃拉托斯坦筛
我有所有可以存储在32位< code>unsigned int中的质数，我想用它们生成一些64位质数。即使在逻辑和编译方面进行了优化，使用试除法还是太慢了。
我正在尝试修改“埃拉托斯特尼筛”以使用预定义列表，如下所示：
- 在阵列A中，从2到4294967291
- 在阵列B中，从2^32到X inc by 1
- 找到C，它是当前素数的第一个倍数
- 从C标记跳转到X。
- 转到1
问题是第3步，它使用模来找到素数倍数，这样的操作是我没有使用轨迹除法的原因。
有没有更好的方法来实现步骤3或整个算法。
谢谢你。
共有1个答案
增加2，而不是1。这是你应该经常使用的最小优化——只考虑可能性。没必要为晚上的事烦恼。
在C中，使用向量
用分段筛预先计算您的核心素数。然后继续使用适合缓存的足够大的段，而无需向核心列表添加新的素数。对于每个素数 p，保持额外的长整型 int 值：它的当前倍数（当然，从素数的平方开始）。步进值是值的两倍 p，或赔率填充筛数组中的 p 偏移量，其中第 i 个条目代表数字 o 2i，o 是小于范围起点的最小奇数。无需按倍数的值排序，核心素数使用的上限单调上升。
sqrt（0xFFFFFFFF）=1048576。PrimePi（1048576）=82025素数是您核心素数列表中所需的全部。那是花生。
< code>long long int的整数算法在您第一次开始(或继续您的工作)时，应该可以很好地找到模，以及范围内的最小倍数。
另请参阅与伪代码相关的答案，以及与C代码相关的答案。
-
我在我的一个班级里做的一个作业，我们必须实现一个厄拉多塞的筛子。我已经尝试了七次来得到一个有效的代码，并且尝试了整合我研究过的许多解决方案。我终于有一个可以输出数字的了。不幸的是，它同时打印合数和质数，但不打印2。 我的代码如下： 我怀疑我的循环有问题。我修复了前两个循环的和变量，以便它从2开始打印出来，问题似乎是在我将数组初始化为true后，它没有将合数标记为。 提前感谢你的帮助。
-
我想创建一个函数，找到所有素数，直到number基于（筛分埃拉托色尼）算法 这是我的代码： 我按部分检查了代码，除了这部分之外，一切都可以正常工作： 代码中没有错误，但是没有输出，我不明白为什么。
-
做一个简单的筛子很容易： 但是当N非常大并且我无法在内存中持有这种数组时，该怎么办？我已经查找了分段筛方法，它们似乎涉及查找素数，直到sqrt（N），但我不明白它是如何工作的。如果 N 非常大（比如 10^18）怎么办？
-
我正在尝试编写一个程序来实现对埃拉托西的筛选。我可以从2到任何给定的结束编号，但我们正在处理的赋值要求我们输入起始值。我完全被卡住了。我试过很多不同的代码，但它总是给我奇怪的答案。 我的起点是起始值，终点是结束值。我基本上想找到这个范围的素数。谢谢！！！
-
在一个类作业中，我被要求用Java编写Eratostenes筛选代码，我的代码效率非常低。运行时间不长，但我相当肯定，除了像我一样列出所有内容外，还有其他循环的空间。。 这是我的代码: 基本上，我所做的是将所有不是质数的元素设置为true… 所以我的主要2个问题是1。有没有办法实现一个循环，使代码更短2。如何打印此数组中所有为 true（质数）的元素
-
我正在尝试让我的埃拉托斯特尼筛程序仅输出用户请求的前n个素数。Sieve本身工作得很好 - 它正确地输出了前100个素数（如下面的数组所示），但是最后一个循环中的计数器变量无法正常工作，我无法找出原因。例如，如果用户输入“5”表示 n，则只会打印前 3 个定焦值。 有人可以帮我找出我的错误吗？我的目的是让“count”成为一个非常简单的计数器，每次都会增加1，直到它达到n。