0

所以我正在尝试编写一个程序来解决最大素数上的 Project 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);
}

问题来自于初筛数组的初始化，因为我省略了那一行之后的所有行，但仍然遇到了问题。我最初使用以下代码声明了数组，该代码对于低至 1000 万的值返回了分段错误。

int primesieve[a+1];

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

4

2 回答 2

0

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

int primesieve[a+1];

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

在堆上分配

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

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

于 2013-10-19T10:00:01.193 回答
0 
600851475143 * sizeof(int64_t) = 4806811801144 = 4.4TB

换句话说，除非您有 5TB 的 RAM，否则此代码将始终崩溃。

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

于 2013-10-19T09:42:20.040 回答