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).
Ako se pravilno ne potkrijepe validnim izvorima, sporne rečenice i navodi mogli bi biti obrisani. 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