0

我无法理解为什么这段代码会出现运行时错误。问题是每个 >=6 的数字都可以表示为两个素数之和。我的代码是......在此先感谢问题链接是http://poj.org/problem?id=2262

#include "stdio.h"
#include "stdlib.h"
#define N 1000000

int main()
{

    long int i,j,k;
    long int *cp = malloc(1000000*sizeof(long int));
    long int *isprime = malloc(1000000*sizeof(long int));
    //long int *isprime;
    long int num,flag;
    //isprime = malloc(2*sizeof(long int));
    for(i=0;i<N;i++)
    {
        isprime[i]=1;
    }
    j=0;
    for(i=2;i<N;i++)
    {
        if(isprime[i])
        {
            cp[j] = i;
            j++;
            for(k=i*i;k<N;k+=i)
            {
                isprime[k] = 0;
            }
        }
    }
    //for(i=0;i<j;i++)
    //{
    //    printf("%d ",cp[i]);
    //}
    //printf("\n");
    while(1)
    {
        scanf("%ld",&num);
        if(num==0) break;
        flag = 0;
        for(i=0;i<j&&num>cp[i];i++)
        {
            //printf("%d ",cp[i]);
            if(isprime[num-cp[i]])
            {
                printf("%ld = %ld + %ld\n",num,cp[i],num-cp[i]);
                flag = 1;
                break;
            }
        }
        if(flag==0)
        {
            printf("Goldbach's conjecture is wrong.\n");
        }
    }
    free(cp);
    free(isprime);
    return 0;
}
4

3 回答 3

1

两种可能性立即浮现在脑海中。首先是如果正在使用的任何测试工具不提供任何输入，则用户输入可能会失败。在不了解安全带的更多细节的情况下，这充其量只是猜测。

您可以通过硬编码一个值而不是从标准输入中接受一个值来检查这一点。

另一种可能性是正在完成相当大的内存分配。可能是您处于不允许这样做的受限环境中。

一个简单的测试是删除的值N（顺便说一下，使用它而不是调用1000000中的多个硬编码数字malloc）。更好的方法是检查返回值malloc以确保它不是 NULL。无论如何都应该这样做。

而且，除此之外，您可能还需要检查您的 Eratosthenes Sieve 代码。应该标记为非素数的第一个项目i是i + i而不是i * i你有的。我认为应该是：

for (k = i + i; k < N; k += i)

数学算法实际上是可以的，因为任何N小于的倍数N * N已经被标记为非素数，因为它是先前检查的素数之一的倍数。

您的问题在于整数溢出。如果您有一个 32 位二进制补码整数（ 的最大值） ，则在N变为的点处，将环绕到。46_349N * N2_148_229_8012_147_483_647-2_146_737_495

发生这种情况时，循环会继续进行，因为该负数仍然小于您的限制，但是我们应该说，将其用作数组索引是不可取的:-)

它适用的原因i + i是因为您的限制远远不足，INT_MAX / 2因此那里不会发生溢出。

如果您想确保在靠近 时这不会成为问题INT_MAX / 2，您可以使用类似的东西：

for (k = i + i; (k < N) && (k > i); k += i)

k如果您的包装遵循“正常”行为，那么额外的检查应该会捕获环绕事件 -从技术上讲，我认为它是未定义的包装行为，但由于两者的补码性质，大多数实现只是将两个正数包装回一个负数。请注意，这实际上是不可移植的，但这实际上意味着它只能在 99.999% 的机器上运行 :-)

但是，如果您是便携性的坚持者，那么首先有更好的方法来防止溢出。我不会在这里讨论它们，但要说它们涉及减去一个被求和的项MAX_INT，并将其与另一个被求和的项进行比较。

于 2013-08-14T07:47:23.413 回答
0

我可以得到这个给出错误的唯一方法是如果我输入一个大于 1000000 或小于 1 的值到 scanf()。

像这样：

ubuntu@amrith:/tmp$ ./x
183475666
Segmentation fault (core dumped)
ubuntu@amrith:/tmp$

但其原因应该是显而易见的。除此之外，这段代码看起来不错。

于 2013-08-14T07:48:06.347 回答
0

只是想找出问题所在！

如果sizeof(long int)它4 bytes适用于您正在使用的操作系统，那么就会出现这个问题。在代码中：

for(k=i*i;k<N;k+=i)
{
    isprime[k] = 0;
}

在这里，当你这样做时k = i*i，对于较大的值 if i，值k会超出4 bytes并被截断，这可能会导致负数，因此，条件k<N得到满足，但有一个负数:)。因此，您会在那里遇到分段错误。

只需要 很好i+i，但是如果您需要增加限制，请注意这个问题。

于 2013-08-14T08:21:51.853 回答