Eratostenovo sito

S Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
Način dobijanja prostih brojeva pomoću Eratostenovog sita

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[uredi | uredi izvor]

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