eratosthenes 计算器筛分法 -- 运行内存问题和数字 >=1,000,000 崩溃

Question

我不确定这是为什么。我尝试将变量更改为 long long，我什至尝试做一些其他事情——但这要么是因为我的代码效率低下（它确实完成了查找所有素数的整个过程，然后检查数字看看它是否能被那个素数整除——效率很低，但这是我第一次尝试，我觉得它能正常工作真是太棒了....)

或者它溢出堆栈的事实。我不确定它到底在哪里，但我所知道的是它必须与内存及其处理数字的方式有关。

如果我不得不猜测，我会说它是在处理直到该数字的素数生成时发生的内存问题——即使我删除了对输入数字的检查，它也会在那里死掉。

我会 post 我的代码 -- 请注意，我没有在几个地方将 long long 变回 int，而且我还有一个未使用的 SquareRoot 变量，因为它应该尝试帮助提高内存效率，但没有像我尝试的那样有效。我只是从未删除过它。如果我能成功完成它，我会清理代码。

据我所知，它在 999,999 及以下的情况下确实非常可靠，我实际上将它与其他相同类型的计算器进行了核对，它似乎确实生成了正确的答案。

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

#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;
        }
    }
}

Answer 1

如果您使用合法的 C++ 构造而不是 non-standard 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 不使用堆栈 space 来分配它的元素（除非你已经为它编写了一个使用堆栈的分配器）。

事实上，您甚至不需要将 upperbound 传递给 sieve，因为 std::vector 通过调用 size() 知道自己的大小成员函数。但我把它留作练习。

Live example using 2,000,000

Answer 2

首先，阅读并应用 PaulMcKenzie 的建议。这是最重要的事情。我只是在解决您仍然悬而未决的问题中的一小部分。

您似乎在尝试分解您误称为 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，如果你愿意的话），其余因子中的 none 可以小于 p。但是，不要忘记 p 作为一个因素可能会出现不止一次。

在任何一轮的程序中你只需要考虑p与当前数的平方根之间的质因数；如果这些质数中的 none 个能整除当前数，那么它一定是质数。要测试 p 是否超过某个数 n 的平方根，您可以使用 if (p * p > n)，这比实际计算平方根的计算效率更高。

因此平方根出现在两个不同的角色中：

要分解的数字的平方根限制了需要进行的筛选量
在试除循环中，当前数的平方根给出了你需要考虑的最高质因数的上限

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

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

上发帖

eratosthenes 计算器筛分法 -- 运行内存问题和数字 >=1,000,000 崩溃

sieve or eratosthenes calculator -- running into memory issues and crashing with numbers >=1,000,000

c++

memory

crash

sieve-of-eratosthenes

eratosthenes 计算器筛分法 -- 运行 内存问题和数字 >=1,000,000 崩溃

sieve or eratosthenes calculator -- running into memory issues and crashing with numbers >=1,000,000

c++

memory

crash

sieve-of-eratosthenes

eratosthenes 计算器筛分法 -- 运行内存问题和数字 >=1,000,000 崩溃