1

我可以猜测它与使用 unsigned long long int 有关。

#include <cstdlib>
#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long int uint64;

int main(int argc, char *argv[])
{



    uint64 number_in_question = 600851475143LL;

    long double sqrt_in_question = sqrt(number_in_question);
    bool primes_array[number_in_question+1];



    for (uint64 i = 0; i <= number_in_question; i++) {
        primes_array[i] = true;
    }

    for (uint64 i = 2; i <= sqrt_in_question; i++) {
        if(primes_array[i] == true) {
            // for every multiple of this prime, mark it as not prime
            for (uint64 ii = i*2; ii <= number_in_question; ii += i) {
                primes_array[ii] = false;           
            }
        }
    }   

    for (uint64 i = 0; i <= number_in_question; i++) {
        if(primes_array[i] == true)
        cout << i << ", ";
    }


    system("PAUSE");


    return EXIT_SUCCESS;
}

Edit1：我正在尝试做的一些背景：

我正在尝试模仿这种技术：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 而我使用数组来存储一个简单的“是素数” 1 表示是，0 表示否。最终目标是解决这个问题：

What is the largest prime factor of the number 600851475143 ?此处列出：http ://projecteuler.net/problem=3 。我只是在研究素数，然后再研究素数。

编辑2：

在查看我发布的 Wikipedia 链接后，我意识到他们有 puesdocode（跳过它并想出了我所拥有的）并意识到有这个注释：大范围可能不完全适合内存。在这些情况下，有必要使用分段筛，一次只筛分范围的一部分。 [14] 对于大到无法将筛选素数保存在内存中的范围，可以使用像 Sorenson 这样的节省空间的筛子。因此，我将不得不想办法使用“分段筛”方法来做到这一点。

编辑3：

更改了数组以考虑 [0] 元素，因此“问题”仅集中在数组内存大小太大而无法将来引用；还将数组存储为 bool 而不是 uint64。

4

3 回答 3

5

您正在尝试分配一个uint64长度数组600851475143。对于 8 字节uint64，这意味着该数组将占用600851475143*8byte大致4.5TB的内存。即使您的系统可以分配那么多内存（不太可能），您也试图将其放在通常只有几 MB 大小的堆栈上。此外，您正在尝试写入 index number_in_question，而数组中的最后一个索引是number_in_question-1。

于 2012-01-12T16:08:27.870 回答
3

我假设您在尝试创建数组时正在炸毁堆栈。数组的大小非常大，必须在堆上创建才能有成功的机会。

于 2012-01-12T16:01:02.920 回答
0

您的数组有“number_in_question”元素，编号为 0 到 number_in_question - 1。但是，如果将分配给您的数组很大，您的 for 循环将尝试访问可用空间之外的 primes_array[number_in_question]。

为什么要分配一个 uint64 数组并在每个元素中存储 0 或 1？

编辑：另外，你不能在堆栈上分配一个可变大小的数组。您必须使用 new 在堆上分配该空间。同样，假设您的系统将允许您分配那么多空间。

于 2012-01-12T16:06:27.020 回答