. غربال اراتوسن

غربال اراتوسن 

«غربال اراتوسن» (Sieve of Eratosthenes) در ریاضیات الگوریتم ساده‌ای است که به‌کمک آن می‌توان تمام اعداد اول تا یک عدد صحیح را یافت. کشف این روش را به «اراتوسن» (Eratosthenes) دانشمند یونان باستان نسبت می‌دهند.
مراحل این الگوریتم به‌صورت ذیل است :

- اعداد بین ۲ تا عدد مورد نظر n را فهرست می‌کنیم.

- دور عدد ۲ خط کشیده و مضرب‌هایش را خط می‌زنیم.

- عدد بعدی در فهرست، یک عدد اول است؛ دور آن خط می‌کشیم.

- تمام مضرب‌های عدد یافت‌شده در مرحله‌ی قبل را خط می‌زنیم.

- مراحل ۳ و ۴ را آن‌قدر تکرار می‌کنیم تا به یک عدد بزرگ‌تر از ریشه‌ی n برسیم. 

- تمام اعداد خط‌نخورده در فهرست، اعداد اول خواهند بود. 

  

منبع : سایت رشد