Eratostenovo sito

Eratostenovo sito je jednostavan algoritam za dobijanje svih prostih brojeva manjih od onog izabranog. Osmislio ga je grčki matematičar, geograf i astronom Eratosten.

 Postupak 

Postupak dobijanja prostih brojeva pomoću Eratostenovog sita:

na papir napišemo sve brojeve od 2 do izabranoga, pa križamo sve sadržaoce broja 2
križamo drugi prosti broj po redu – broj 3, a zatim sve njegove sadržaoce
isti postupak ponovimo s brojem 5
isti postupak ponovimo s brojem 7
svi brojevi koji su ostali su prosti brojevi

Primjer dijela suštine koda napisanog u C jeziku:

    int i=0, n=2;
    printf("Unesite do kojeg broja zelite proste brojeve: ");
    scanf("%d",&n);
    printf("Prosti brojevi do %d su: \n",n);

   for(i=2; i<=n; i++)                                    //vrti brojeve
   if((i!=2)&&(i!=3)&&(i!=5)&&(i!=7))                     //2,3,5,7 su prosti
   {
   if((i%2!=0)&&(i%3!=0)&&(i%5!=0)&&(i%7!=0))             //eratostenovo sito,
   printf("%d ",i);                                       //ako nisu djeljivi sa
   }                                                      //2,3,5 i 7 nisu prosti
   else printf("%d ",i);                                  //printa 2,3,5,7

Kategorija:Testovi primaliteta
Kategorija:Teorija sita
Kategorija:Algoritmi