最初の素数は常に2の代わりに1になります

Question

ここで私はerastostheneの篩をcで実装しようとしています。プログラムは1つの大きな問題以外はうまくいきます。最初の素数を値2に手動で設定します。最後にすべての素数配列をループして印刷すると、最初の値は2ではなく1になります。なぜこの問題が発生するのか把握できません。

#include<stdio.h> 
#include<math.h> 
int main(){ 

    int n = 64; 
    int i,j,limit=sqrt(n)+2,nPrime=0; 
    int prime[50]={0},mark[64]={0}; 
    mark[1]=1; 

    prime[nPrime++] = 2; 
    printf("%d\n",prime[0]); // initialized to 2 



    for(i=4;i<=n;i=i+2){ 
     mark[i] = 1; 
    } 
    for(i=3;i<=n;i=i+2){ 
     if(!mark[i]){ 
      prime[nPrime++] = i; 
      if(i<=limit){ 
       for(j=i*i;j<=n;j=j+i*2){ 
       mark[j]=1; 
       } 
      } 
     } 
    } 
    int k; 
    int size = sizeof(prime)/sizeof(prime[0]); 
    printf("%d\n",prime[0]); // changed to 1; 
    for(k=0;k<size && prime[k]!=0;k++){ 
     printf("%d ",prime[k]); 
    } 

} 

Answer 1

問題は、このループである：

for(i=4;i<=n;i=i+2) { 
    mark[i] = 1; 
} 

<=でそれが値64を取る、それが範囲外になるので条件は、i < nする必要があります。

mark[64] = 1を設定すると、マーク配列に属していないメモリが変更されます。この場合は、プライム配列の最初の要素になります。他のインデックスをテストすると、セグメンテーションを取得する可能性があります。

手動mark[64] = 56を設定する場合、次のように表示されます、ローカル変数がスタック上に宣言されているprime[0] == 56

Answer 2

ので、あなたのケースで変数mark [64] 64整数（64 * 4 = 256バイトの配列であります以下に示すように）スタックの最初の256バイトを占め、配列プライムは、（50 * 4 = 200バイト）の次の200バイトを占め：

      Stack 
         |-----------| 
         | other | 
         | variables | 
         |   | 
      prime[49]->|-----------| addr = 0x000001C8 
         |   | 
         | prime | 
         |(200 bytes)| 
      prime[0]->|   | 
      mark[63]->|-----------| addr = 0x00000100 
         |   | 
         |   | 
         | mark | 
         |(256 bytes)| 
         |   | 
       mark[0]->|-----------| addr = 0x00000000 

に[64] = 1マークを記述する場合、あなたが実際にありますプライム[0] = 1の4バイトを書き込みます。