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，并且不检查余数，只需删除号码。