代码之家 › 专栏 › 技术社区 › spiroth10

筛选或删除thenes计算器--遇到内存问题并导致大于等于1000000的数字崩溃

sieve-of-eratosthenes crash memory c++

-3

spiroth10 · 技术社区 · 9 年前

我不确定为什么会这样。我试着把变量改为long-long,我甚至尝试做了一些其他的事情——但这要么是因为我的代码效率低下(它实际上完成了查找所有素数的整个过程,然后检查这个数是否可以被这个素数整除——效率很低,但这是我第一次尝试,我觉得让它工作起来很有成就感……)

或者它溢出堆栈的事实。我不确定它到底在哪里,但我所知道的是,它一定与记忆和它处理数字的方式有关。

如果我必须猜测的话,我会说这是一个内存问题,当它处理直到那个数字的素数生成时——这就是它死掉的地方,即使我去掉了对输入数字的检查。

我会发布我的代码——请注意,我在几个地方并没有很长时间改回int,而且我还有一个SquareRoot变量没有被使用,因为它本来是用来帮助内存效率的,但我尝试的方式并不有效。我从未删除过它。如果我能成功地完成代码,我会清理代码。

不过,据我所知,它在999999及以下的情况下确实非常可靠,我实际上将它与其他同类计算器进行了比较,它似乎确实生成了正确的答案。

如果有人能帮助或解释我在这里搞砸了什么,你可以帮助一个在没有任何学校或任何东西的情况下试图独自学习的人。所以很感激。

#include <iostream>
#include <cmath>

void sieve(int ubound, int primes[]);

int main()
{
    long long n;
    int i;
    std::cout << "Input Number: ";
    std::cin >> n;

    if (n < 2) {
        return 1;
    }

    long long upperbound = n;
    int A[upperbound];
    int SquareRoot = sqrt(upperbound);
    sieve(upperbound, A);

    for (i = 0; i < upperbound; i++) {
        if (A[i] == 1 && upperbound % i == 0) {
            std::cout << " " << i << " ";
        }
    }
    return 0;
}

void sieve(int ubound, int primes[])
{
    long long i, j, m;

    for (i = 0; i < ubound; i++) {
        primes[i] = 1;
    }

    primes[0] = 0, primes[1] = 0;

    for (i = 2; i < ubound; i++) {
        for(j = i * i; j < ubound; j += i) {
            primes[j] = 0;
        }
    }
}

2 回复 | 直到 9 年前

1

Community CDub 8 年前

如果您使用合法的C++构造而不是非标准的 variable length arrays ,您的代码将运行(是否生成正确答案是另一个问题)。

问题很可能是,当您声明包含一百万或更多元素的数组时,您超出了堆栈的限制。

因此,与其这样:

long long upperbound = n;
A[upperbound];

使用 std::vector :

#include <vector>
//...
long long upperbound = n;
std::vector<int> A(upperbound);

然后:

sieve(upperbound, A.data());

这个 std::vector 不使用堆栈空间来分配其元素(除非您为其编写了使用堆栈的分配器)。

事实上,你甚至不需要通过 upperbound 到 sieve ,作为 std::矢量 通过调用 size() 成员函数。但我把它作为一个练习。

Live example using 2,000,000

2

0

Community CDub 8 年前

首先,阅读并应用保罗·麦肯齐的建议。这是最重要的。我只是在回答你的问题中一些尚未解决的小问题。

你似乎在试图考虑你误导性地拨打的电话号码 upperbound 这个数的平方根的神秘作用与这个事实有关:如果这个数完全是复合的-因此可以计算为某些质因子的乘积-那么这些质因子中最小的一个不可能大于这个数的方根。事实上,只有一个因素可能更大,所有其他因素都不能超过平方根。

然而,以目前的形式,您的代码无法从这一事实中获益。现在的审判循环必须达到 number_to_be_factored / 2 为了不错过任何因素,因为它的身体看起来像这样:

if (sieve[i] == 1 && number_to_be_factored % i == 0) {
   std::cout << " " << i << " ";
}

如果你稍微重构一下代码,你可以更有效地进行因子分析:当你找到了数字中最小的素因子p时,剩下的因子就必须是 rest = number_to_be_factored / p (或 n = n / p ,如果你愿意的话),其余的因素都不能小于p。但是,不要忘记p可能会作为一个因素出现不止一次。

在任何一轮程序中,你只需要考虑p和当前数的平方根之间的素因子;如果这些素数中没有一个除当前数,那么它一定是素数。要测试p是否超过某个数n的平方根,可以使用 if (p * p > n) ,这在计算上比实际计算平方根更有效。

因此,平方根有两种不同的作用:

要计算的数值的平方根限制了需要进行的筛分量
在试算除法循环中,当前数的平方根给出了需要考虑的最高素因子的上界

这是同一枚硬币的两面,但在实际代码中有两种不同的用法。

注意:一旦你通过应用PaulMcKenzie的建议使代码正常工作,你也可以考虑在 Code Review .