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

از ویکیجو | دانشنامه آزاد پارسی

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

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

 


  1. prime numbers
  2. sequence
  3. integers
  4. multiple
  5. even numbers