这是MinGW的错误吗？

Question

我一直试图通过Code :: Blocks在我的MinGW上执行这个程序:

#include <string.h>
#include <math.h>
#include <stdio.h>
#define N 100
int p[N];
int pr[N];
int cnt;

void sieve()
{
   int i,j;
   for(i=0;i<N;i++) pr[i]=1;
   pr[0]=pr[1]=0;

   for(i=2;i<N;i++)
      if(pr[i])
        {
         p[cnt]=i; cnt++;
         for(j=i+i;j<=N;j+=i) pr[j]=0;
        }

  }

int main(){
    sieve();
    int i;
    for(i=0;i<cnt;i++)
       printf("%d ",p[i]);
    puts("");
   printf("Total number of prime numbers : %d",cnt);
  return 0;
}

在我的系统上输出是:

7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
素数总数:22

这完全是疯了,因为我完全确定我的算法的实现.

所以我决定在Ideone中尝试它,它提供正确的输出.任何人都可以指出原因吗？

我将其更改为N,但输出不会改变.

Answer 1

不,它实际上被称为Debanjan错误:-)看看这个:

#define N 100
int p[N / 64];

它看起来像你只允许足够的空间来存储数组中的一个素数p.这意味着写入p[X]for X > 0可能会覆盖其他值.

这是可怕的未定义行为,这意味着任何事情都可能发生(包括它在Ideone情况下工作).

只需使用:

int p[N];

声明数组.我很确定不会超过100个小于或等于100的素数:-)

Answer 2

您的代码中有两个重要的错误.

一个是你的p数组太小了,所以你要写下它的结尾.这是未定义的行为,但在您使用它的平台上会覆盖pr数组的开头.这对输出没有影响,因为您要覆盖的位置在您在筛子中测试的位置之前.

另一个是你也在写下pr数组的结尾:

        for(j=i+i;j<=N;j+=i) pr[j]=0;

这个循环设置pr[N]为零,这是在结束时pr.在MinGW中,这是cnt存储的位置,因此每次i分割N时cnt都设置为零.和N100一样,这发生在i==2和i==5,所以你在结果前五次失去素数.IdeOne似乎把它cnt放在其他地方pr,所以它不会被覆盖.这就是您使用不同编译器获得不同输出的原因.

将数组p的大小更改为N,或者仅对筛选和输出使用一个数组,并<=在第18行中更改为<不要将其结束.

int p[N];
int *pr = p; // reuse the array