Sita e Eratostenit

Sita e  Eratostenit është një algoritëm i thjeshtë dhe mjaft i vjetër për gjetjen e numrave të thjeshtë më të vegjël se një numër i caktuar natyral.Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους  or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers," Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.
Ai është shumë efikas për numrat më të vegjël se  10 milion).The Prime Glossary: "The Sieve of Eratosthenes", 
http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
Algoritmi u zbulua nga matematikani antik grek  Eratosteni. Nicomachus, Introduction to Arithmetic, I, 13.  

 Algoritmi 

Numri i thjeshtë është numri i cili ka pikërisht dy pjesëtues numrin 1 dhe vetveten.

Për të gjetur numrat e thjeshtë më të vegjël ose të barabartë me numrin e dhënë sipas metodës së Eratostenit kemi:

 Krijojmë listën e të gjithë numrave natyrorë prej numrit 2 deri te numri i dëshiruar  n: (2, 3, 4, ... , n).
 Numri i parë i thjeshtë është 2.
 I heqim nga lista të gjithë shumëfishat e p më të vegjël ose të barabartë me n.
 E vërejmë numrin e mbetur në listë që është më i madh se p (ai është i thjeshtë) ; e zëvendësojmë atë me p.
 Hapat 3 dhe 4 i përsërisim derisa  p2 është më i madh se n.
 Të gjithë numrat e mbetur janë të thjeshtë.

Shembull

Për të gjetur numrat e thjeshtë më të vegjël se 30 veprojmë kështu:

E shkruajmë listën e numrave natyrorë nga 2 deri në  30:

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

I largojmë shumëfishat e dyshit atëherë kemi listën:

  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

Numri i parë pas 2 është 3 ai është i thjeshtë, në vazhdim i largojmë shumëfishat e 3 atëherë kemi listën:

  2  3     5     7          11    13          17    19          23    25          29

Numri që vjen pas 3 është 5 i cili është i thjeshtë pastaj nga lista e mësipërme i largojmë shumëfishat e 5 dhe atëherë fitojmë këtë listë:

  2  3     5     7          11    13          17    19          23                29

Numri që vjen pas 5 është 7 por pasi >30 procesi këtu përfundon që do të thotë se në listën e mësipërme të gjithë numrat janë të thjeshtë dhe më të vegjël se 30.

Referimet

Lidhje të jashtme
 Sieve of Eratosthenes in C
 Sieve of Eratosthenes  in PHP
 Analyze the Sieve of Eratosthenes in an online Javascript IDE
 Interactive JavaScript Page
 Sieve of Eratosthenes nga George Beck.
 Sieve of Eratosthenes algorithm illustrated and explained. Java and C++ implementations.

Kategoria:Matematikë
Kategoria:Greqia e Lashtë