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

غَربال اِراتُسْتِن (Eratosthenes\' sieve)

روشی برای یافتن اعداد اول تا عددی مفروض. روش کار به این صورت است که دنبالۀ همۀ عددهای صحیح از ۲ تا عدد مفروض را می‌نویسیم. سپس، ۲ را که اول است نگه‌می‌داریم و عددهای بعدی را دوتادو شمرده، هربار دومی را حذف می‌کنیم. به این‌ترتیب، همۀ مضربهای ۲ (عددهای زوج) حذف می‌شوند. آن‌گاه، اولین عدد باقی‌مانده یعنی ۳ را که اول است نگه‌می‌داریم و بقیۀ عددها را سه‌تا سه‌تا شمرده هربار سومی را حذف می‌کنیم. مضرب‌های زوج ۳ نیز قبلاً حذف شده‌اند. بعد به سراغ ۵ می‌رویم که بر ۲ و ۳ تقسیم‌پذیر نیست، وگرنه قبلاً حذف شده‌ بود. آن‌ را نگه ‌می‌داریم و از اعداد باقی ‌ماندۀ بعدی همۀ مضرب‌های ۵ را حذف می‌کنیم. این کار را برای ۷، ۱۱، ۱۳ و ... تکرار می‌کنیم. عددهایی که می‌مانند، اول‌اند.

 

---