Sita E Eratostenit

Ai është shumë efikas për numrat më të vegjël se 10 milion). Algoritmi u zbulua nga matematikani antik grek Eratosteni.

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

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

1. Krijojmë listën e të gjithë numrave natyral prej numrit 2 deri te numri i dëshiruar n: (2, 3, 4, ... , n).
2. Numri i parë i thjeshtë është 2.
3. I flakim nga lista të gjithë shumëfishat e p më të vegjël ose të barabartë me n.
4. 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.
5. Hapat 3 dhe 4 i përsërisim derisa p² është më i madh se n.
6. 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 natyral 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 ${\displaystyle 7^{2}=49}$ >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.

• 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.