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.[1] Ai është shumë efikas për numrat më të vegjël se 10 milion).[2] Algoritmi u zbulua nga matematikani antik grek Eratosteni.[3]
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.
- ↑ 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.
- ↑ The Prime Glossary: "The Sieve of Eratosthenes", http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes, references 16. November 2008.
- ↑ Nicomachus, Introduction to Arithmetic, I, 13. [1]