Eratostenovo sito

Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). Ako se pravilno ne potkrijepe pouzdanim izvorima, sporne rečenice i navodi mogli bi biti izbrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

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 dobijanja prostih brojeva pomoću Eratostenovog sita:

1. na papir napišemo sve brojeve od 2 do izabranoga, pa križamo sve sadržaoce broja 2
2. križamo drugi prosti broj po redu – broj 3, a zatim sve njegove sadržaoce
3. isti postupak ponovimo s brojem 5
4. isti postupak ponovimo s brojem 7
5. 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