爲什麼第一個素數總是變成1而不是2

這裏我試圖在c中實現erastosthene篩選。除了一個主要問題外，程序工作正常。我手動將第一個素數設置爲值2。當我循環遍歷所有素數數組並打印它們時，第一個值變爲1而不是2.無法找出爲什麼會出現此問題。任何幫助都將非常感謝。爲什麼第一個素數總是變成1而不是2

#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]); 
    } 

}

來源

2016-10-22 AL-zami

此違反（i = 4; i <= n; i = i + 2）mark [i] = 1;'。該數組只有64個元素，索引從0..63。上面的循環會寫入'mark [64]'，調用*未定義的行爲*（並覆蓋您的'prime'插槽0作爲獎勵.'''應該是'<'。 – WhozCraig

好的，謝謝...但爲什麼它會覆蓋素數組？：| –

因爲它*可以* .UB調用意味着*任何*可能發生（包括不幸的情況，它甚至似乎工作*正確*）。在架構上可能依賴於自動變量被分配到它們的實現堆棧空間中，很高興你抓住了它，UB是沒有趣味的地方。 – WhozCraig

的問題是在這個循環：

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

條件應該是i < n，因爲它<=將採取值64，這將是出界。

當您設置mark[64] = 1您正在修改不屬於標記數組的內存，在這種情況下，它將變爲質數組的第一個元素。如果你測試了其他索引，最終可能會出現段錯誤。

如果設置手動mark[64] = 56，你會看到prime[0] == 56

來源

2016-10-22 09:32:38 diugalde

因爲局部變量聲明上堆疊，你的情況的可變標記[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時，實際上寫入素數[4]的四個字節= 1.

來源

2016-10-22 10:20:19 shamba

爲什麼第一個素數總是變成1而不是2

回答

相關問題