Sieve of Erastosthenes Algorithm

[huangblue]

Sieve of Erastosthenes Algorithm

To Display All Prime Numbers Between 1 and n Step 1: Define an array of integers P. Set all elements Pi to 0, 2 <= i <= n. Step 2: Set i to 2. Step 3: If i > n, the algorithm terminates. Step 4: If Pi is 0, then i is prime. Step 5: For all positive integer values of j, such that i x j ≤ n, set Pixj to 1. Step 6: Add 1 to i and go to step 3.

[huangblue]

//阅读版本

include

int main (void) { 　 int i,j,n=150; 　 _Bool flag[n]; 　 int P[n]; 　 for (i=2;i<n;i++){ 　　 P[i]=0; 　　 flag[i]=0; 　 } 　 i=2; 　 while (i<=n){ 　　 if (P[i]==0){flag[i]=1;} 　　 for (j=1;i*j<n;j++){ 　　　 P[i*j]=1; 　　 } 　　 ++i; 　 } 　 for (i=2;i<n;i++){ 　　 if ( flag[i]){ 　　　 printf("%i,",i); 　　 }

　 } 　 return 0; }

[huangblue]

//运行版本

include

int main (void) { 　 int i,j,n=150; 　 _Bool flag[n]; 　 int P[n]; 　 for (i=2;i<n;i++){ 　　 P[i]=0; 　　 flag[i]=0; 　 } 　 i=2; 　 while (i<=n){ 　　 if (P[i]==0){flag[i]=1;} 　　 for (j=1;ij<n;j++){ 　　　 P[ij]=1; 　　 } 　　 ++i; 　 } 　 for (i=2;i<n;i++){ 　　 if ( flag[i]){ 　　　 printf("%i,",i); 　　 }

　 } 　 return 0; }