C：使用數組的Eratosthenes篩選

Question

我正在研究C編程任務來實現Eratosthenes的Sieve，而不使用C的平方根函數。下面是我的輸出和我的教授輸出，我不確定我的代碼中有什麼導致它是錯誤的。有任何想法嗎？

這裏的預期輸出

Program initiated 
    1 2 3 5 7 11 13 17 19 23 29 31 
    37 41 43 47 53 59 61 67 71 73 79 83 
    89 97 101 103 107 109 113 127 131 137 139 149 
151 157 163 167 173 179 181 191 193 197 199 211 
223 227 229 233 239 241 251 257 263 269 271 277 
281 283 293 307 311 313 317 331 337 347 349 353 
359 367 373 379 383 389 397 401 409 419 421 431 
433 439 443 449 457 461 463 467 479 487 491 499 
503 509 521 523 541 547 557 563 569 571 577 587 
593 599 601 607 613 617 619 631 641 643 647 653 
659 661 673 677 683 691 701 709 719 727 733 739 
743 751 757 761 769 773 787 797 809 811 821 823 
827 829 839 853 857 859 863 877 881 883 887 
Program terminated 

這裏是我的輸出：

Program initiated 
    1 37 41 43 47 53 59 61 67 71 73 79 
    83 89 97 101 103 107 109 113 127 131 137 139 
149 151 157 163 167 173 179 181 191 193 197 199 
211 223 227 229 233 239 241 251 257 263 269 271 
277 281 283 293 307 311 313 317 331 337 347 349 
353 359 367 373 379 383 389 397 401 409 419 421 
431 433 439 443 449 457 461 463 467 479 487 491 
499 503 509 521 523 541 547 557 563 569 571 577 
587 593 599 601 607 613 617 619 631 641 643 647 
653 659 661 673 677 683 691 701 709 719 727 733 
739 743 751 757 761 769 773 787 797 809 811 821 
823 827 829 839 853 857 859 863 877 881 883 887 
Program terminated 

這裏是我的代碼：

#include <stdio.h> 

void zap(int data[], int divisor) 
{ 
    for(int i=0;i<900;i++) 
    { 
     if(data[i]%divisor==0) // if mod is not 0, 0 out the index. 
     { 
      data[i] = 0; 
     } 
    } 
} 
// the display method 
void display(int data[]) 
{ 
    int count = 0; // init counter on the out side 
    for(int i=0;i<900;i++) 
    { 
     if(data[i]>0)// don't print 0s 
     { 
      printf("%4d",data[i]);// print the data in a column 

      count++;// increment count 

      if(count==12) // print rows and columns 
      { 
       count=0; // reset count 
       printf("\n"); // print new line 
      } 
     } 
    } 
    if(count<12)// we terminate loop and we now need print a new line 
    { 
     printf("\n"); 
    } 
} 

int main() 
{ 
    // start the program, with a message 
    printf("Program initiated\n"); 

    // needs to be 900 long 
    int primes[900]; 

    // populate the array 
    for(int i=1; i <= 900; i++) 
    { 
      primes[i] = i; 
    } 

    // elminate the bad numbers 
    for(int i=2; i < 35; i++) 
    { 
     zap(primes,i); 
    } 

    // display the array. 
    display(primes); 

    // print the end message  
    printf("Program terminated\n"); 

    return 0; 
} 

Answer 1

好，你可以可以使用這樣的事情：

（初始化篩是一個足夠大的布爾陣列設置爲true每個條目 - 因爲我要保持它的簡單集合sieve[0] = false; sieve[1] = false;

for(int i = 2; i < endOfNumbers; i++) 
{ 
    if (sieve[i] == false) continue; 
    for (int m = 2*i; m < endOfNumbers; m += i) 
     sieve[m]=false; 
} 

Answer 2

你zap函數總是扎普的輸入值。例如，當你用除數2調用zap時，它將檢查2%2，找到0，然後將其置1，儘管2是質數。

要解決這個問題，你應該讓它開始在divisor+1。

但是，我注意到它實際上並沒有在做Sieve。 zap應該不需要做任何模數，只需步行divisor即可。仔細檢查一下Eratosthenes的Sieve實際上是什麼。

Answer 3

這個算法不是真正的Eratosthenes篩選算法，這個算法的目的是爲了避免測試可分性（與%）完全由一味地（即沒有任何計算）排除除2之外的每個第二個數字，然後每3個除外3，然後每4除了4等等。

您需要修復zap函數：首先，不要刪除號碼，如果它等於divisor，並且不檢查餘數，只需刪除號碼。