This procedure is called sieve of Eratosthenes.

Implement the following procedure to generate prime numbers from 1 to 100 into a program. This procedure is called sieve of Eratosthenes.

step 1

Fill an array num[100] with numbers from 1 to 100

step 2

Starting with the second entry in the array, set all its multiples to zero.

step 3

Proceed to the next non-zero element and set all its multiples to zero.

step 4

Repeat step 3 till you have set up the multiples of all the non-zero elements to zero

step 5

At the conclusion of step 4, all the non-zero entries left in the array would be prime numbers, so print out these numbers.

 

Code:-

 

#include<stdio.h>
#include<conio.h>

void main() {

int i,j,a[100];
clrscr();

for(i=0;i<100;i++) {

a[i]=i+1;

}

printf("\n100 numbers in the array:\n\n");

for(i=0;i<100;i++) {

printf("%3d ",a[i]);

}

printf("\n\nafter implementing eratothene's sieve:\n\n");

for(i=2;i<100;i++) {

for(j=2;j<a[i];j++) {

if(a[i]%j==0)
a[i]=0;
}
}

i=a[0];
for(;i<100;i++) {


printf("%3d ",a[i]);

}

printf("\n\nprime numbers are: \n\n");

for(i=a[0];i<100;i++) {

if(a[i]!=0)

printf("%3d ",a[i]);

}

getch();
}
 

 Output:-

 

Previous Next