在C++中初始化数组时的Seg故障(Project Euler Number 3)

Question

因此，我试图编写一个程序，以最大素因子来解决Euler项目问题，虽然我知道代码在结构上是正确的(只要它返回较小数字的正确答案，包括它们给出的示例13195 )，当我输入我们应该解决的数字，即600851475143时，我一直收到一个分段错误。守则如下：

#include <stdio.h>
#include <math.h>

main(){
    int number,a,b,c,i,j,n,gpf;
    printf("Input number to analyze: ");
    scanf("%d",&number);
    a = number/2;
    printf("%d\n",a);
    int* primesieve = new int[a+1];               /*IMPORTANT LINE*/
    for (i=0;i<a+1;i++){
        primesieve[i] = 1;
    }
    for (j=2;j<=a;j++){
        if (primesieve[j] == 1){
            for (c=2;j*c<=a;c++){
                primesieve[j*c] = 0;
            }
        }
    }
    for (n=2;n<=a;n++){
        b = number/n;
        printf("%d\n",b);
        if (number % n == 0){
            if (primesieve[b] == 1){
                gpf = b;
                n = a+1;
            }
        }
    }
    delete[] primesieve;
    printf("The greatest prime factor of %d is %d.\n",number,gpf);
}

这个问题来自于主筛数组的初始化，因为我忽略了之后的所有行，并且仍然遇到了这个问题。我最初使用以下代码声明数组，该代码返回值低至1 000万的分段错误。

int primesieve[a+1];

我在这个站点上搜索了一个解决方案，这导致了对动态数组分配的更改，但是虽然这解决了1000万的问题，但它显然没有得到更大的值。我注意到的其他解决方案提到了使用malloc()或在main()之外静态声明数组，但坦率地说，我不理解这些，因为我的入门编程类几乎没有提到malloc()，我认为导致数组声明的代码需要包含在main()中。(供参考：Segmentation Fault While Creating Large Arrays in C和Seg Fault when initializing array.)我确信这是一个相当简单的问题，但我是一个相对较新的程序员，因此对分配内存的理解很差，所以我发现的任何建议、解决方案或对其他解决方案的解释都将不胜感激。

Answer 1

您的经验与您的编译器的物理限制和精度有关。第一次尝试，在堆栈上分配数组。

int primesieve[a+1];

很快就失败了，因为在大多数系统中，与堆相比，堆栈的大小是相当有限的。

在堆上分配

int* primesieve = new int[a+1]; 

给您更多的空间，但您仍然有可寻址内存的限制。现在，600851475143是一个相当大的数字，即使除以它2，假设int的大小是4个字节，您可能会想，您是否真的能够处理那么多内存。使用32位，您可以寻址2^32 = 4294967296字节。

Answer 2

600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB

换句话说，除非您有5TB的RAM，否则这段代码总是会崩溃。

如果你用位图作为你的筛子，你可以让它更容易忍受。例如，使用每个数字1位，而不是映射甚至是数字，只需要内存的600851475143 / 8 / 2 = 35GB。仍然很多，但可行的，如果你有一些钱的硬件。