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.

Način dobijanja prostih brojeva pomoću Eratostenovog sita

Postupak

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