Eratostenovo sito

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.
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