غربال اراتوستن
غربال اراتوستن، در ریاضیات، الگوریتم سادهای است که با کمک آن میتوان اعداد اول موجود در یک مجموعه متوالی و متناهی از اعداد طبیعی را مشخص کرد. کشف این روش را به اراتوستن دانشمند یونان باستان نسبت میدهند.
![](http://upload.wikimedia.org/wikipedia/commons/b/b9/Sieve_of_Eratosthenes_animation.gif)
برای استفاده از این غربال باید از هفت قانون زیر پیروی کرد. (فرض کنید میخواهیم اعداد اول بین 1 تا 120 را بیابیم):
- عددهای 1 تا 120 را مینویسیم.
- عدد 1 را خط میزنیم.
- دور عدد 2 خط میکشیم و مضربهایش را خط میزنیم.
- دور عدد اول بعدی خط میکشیم و مضربهایش را خط میزنیم.
- بازگشت به مرحله چهارم.
- این کار را تا جایی که به عدد اولی برسیم که توان دوم آن عدد در میان اعداد وجود نداشته باشد ادامه میدهیم.
- دور تمام اعداد باقی مانده خط میکشیم و حالا دیگر میدانیم که اعداد اول کدامها هستند.
منابع
ویرایش- Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an Account of His Method of Finding All the Prime Numbers, by the Rev. Samuel Horsley, F. R. S. , Philosophical Transactions (1683-1775), Vol. 62. (1772), pp. 327-347.