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

غربال اراتستن، در ریاضیات، الگوریتم ساده‌ای است که با کمک آن می‌توان اعداد اول بین اعداد مختلف را یافت. کشف این روش را به اراتستن دانشمند یونان باستان نسبت می‌دهند.

نمایش متحرک غربال اراتستن. اعدادی که در پایان در سمت راست جدول نوشته می‌شوند اول هستند.

برای استفاده از این غربال باید از هفت قانون زیر پیروی کرد .(فرض کنید می‌خواهیم اعداد اول بین 1 تا 120 را بیابیم):

  1. اعداد بین 1 تا 120 را می‌نویسیم.
  2. عدد 1 را خط می‌زنیم.
  3. دور عدد 2 خط می‌کشیم و مضرب‌هایش را خط می‌زنیم.
  4. دور عدد اول بعدی خط می‌کشیم و مضرب‌هایش را خط می‌زنیم.
  5. بازگشت به مرحله چهارم.
  6. این کار را تا جایی که به عدد اولی برسیم که مضرب‌هایش در جدول خط نخورده باشد انجام می‌دهیم.
  7. دور تمام اعداد باقی مانده خط می‌کشیم.

منابع
  • Κόσκινον Ερατοσθένους 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.


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.