- c - 在位数组中找到第一个零
- linux - Unix 显示有关匹配两种模式之一的文件的信息
- 正则表达式替换多个文件
- linux - 隐藏来自 xtrace 的命令
我正在研究一个简单的埃拉托色尼筛法算法,代码如下:
int main()
{
const int n = 1000000;
int sqrn = floor(sqrt(n));
bool primes[n + 1] = { 0 }; // false means prime, true not prime
primes[0] = true;
primes[1] = true;
for (int i = 2; i <= sqrn; i++){
if (primes[i] == false) {
int j = i + i;
while (j<=n-1){
primes[j] = true;
j = j + i;
}
}
}
}
我的主要问题是,如果我尝试将搜索数组设置为大于 n=1000000,此代码会导致堆栈溢出错误。我不确定这是因为编程错误还是因为程序无法容纳大于 10^6 条目的 bool 数组?任何建议表示赞赏。
我的另一个小问题是,在 for 循环语句之外设置 n 的平方根的计算是否可以提高执行速度。
谢谢
最佳答案
您正在堆栈上分配 primes
数组。堆栈只有有限的大小(它相当大,但仍然有限)。您可以:
new
在堆上分配数组关于C++ Sieve of Eratosthenes算法导致堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23353802/
根据链接:http://en.wikipedia.org/wiki/Sieve_of_Sundaram,用于生成最多为 n 的素数列表的“sundaram 筛法”的运行时间为 O(n*log(n))。
我目前正在尝试比较两种不同素数生成算法的平均运行速度。我有这个简单的埃拉托色尼筛法实现: std::vector sieve_of_eratosthenes(int32_t n) { std:
我正在研究一个简单的埃拉托色尼筛法算法,代码如下: int main() { const int n = 1000000; int sqrn = floor(sqrt(n));
当我偶然发现一种称为欧拉筛的改进版的埃拉托色尼筛时,我正在阅读不同的筛分算法。根据Wikipedia在 Haskell 中有一个稍微不同版本的想法(称为 Turner's Sieve)的实现。 现在我
这是我编写的用于在上限可以大到 1000000000 的范围之间查找素数的代码。我使用了 Hashmap,除了 2 之外没有存储任何偶数,也没有存储 sero 和 1但当我使用输入 lb = 1 和
我最近编写了这段代码,但想知道是否有更快的方法来查找素数(不是筛子;我仍在尝试实现)。有什么建议吗?我正在使用 Python,而且对它还很陌生。 def isPrime(input): cur
我正在编写一种方法来查找不超过 n(埃拉托色尼筛法)的素数,是的,这是作业。我希望提高我编写的方法的性能。最近几天我一直在调整它,但无法遵循给出的伪代码并提高性能。 伪代码如下: 创建要处理的号码队列
目前我有两个功能: 一个需要生成素数的数量。 第二个取素数上限生成。 它们是这样编码的(在 C++ 中): prime_list erato_sieve(ul_it upper_limit) {
我一直在研究 Stroustrup 的书: http://www.amazon.com/Programming-Principles-Practice-Using-C/dp/0321543726我目前
我正在尝试使用筛子打印出一组特定的素数,但我似乎没有得到任何输出,但它编译正常。程序不会退出,除非我强制执行,所以我猜它卡在了某个地方...我该如何解决这个问题? #include #include
我编写了以下代码,使用 Sieve 的方法列出了 20 亿以内的所有质数。我使用位掩码来标记目的。虽然我能够正确地得到素数,但每次都会丢失一些开头的素数。请帮我找出程序中的错误。 #include
来自 Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. 你是如何做到这一点的? 复杂性
来自 Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. 你是如何做到这一点的? 复杂性
我正在尝试实现 Sieve of Eratosthene在 C++ 中。但是,经过多次尝试后,我总是会遇到运行时错误。我认为这与正在使用的迭代器的状态在某处损坏有关。我不能把我的手指放在上面。这是我的
最近我一直在研究使用阿特金筛 (http://en.wikipedia.org/wiki/Sieve_of_atkin) 生成其素数的 C++ 素数生成器。我的目标是能够生成任何 32 位数字。我将主
我正在尝试理解“Eratosthenes 筛法”。这是我的算法(下面的代码),以及我无法理解的功能列表(按顺序)。 为什么 i * i 比 i * 2 更有效?是的,我可以理解它会减少迭代次数,因此效
我用 Java 编写了以下“分段筛”程序。它需要筛选一系列数字,使用“筛选素数”(素数数组列表变量)划掉复合数,然后返回尚未划掉的素数。这是代码: public ArrayList sieveWork
我更多地来自 java/php 背景,我现在正在学习 C++。我试图用 C++ 重新创建埃拉托色尼筛法并打印出 5000 以下的所有素数。 我正在用 http://www.compileonline.
我想首先说明我是一个 python 新手,我很感激任何能向我清楚、完整地解释它的人。 我正在查看以下链接中的代码: http://rosettacode.org/wiki/Sieve_of_Erato
我正在研究 PrimeSieve 的数组列表实现,我已经编写了所有代码,但它似乎无法运行,所以我不确定是因为循环不好还是因为我设置了错误的扫描器。 这是代码。 import java.util.S
我是一名优秀的程序员,十分优秀!