تدریس ریاضی

الگوریتم غربال اراتوستن: کشف اعداد اول با یک روش هوشمندانه

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

چگونه کار می‌کند؟

فرض کنید می‌خواهیم تمام اعداد اول تا 100 را پیدا کنیم:

1. لیستی از اعداد 2 تا 100 بسازید (چون 1 اول نیست و اعداد زوج جز 2 اول نیستند).

2. کوچک‌ترین عدد باقی‌مانده که هنوز خط نخورده را انتخاب کنید (ابتدا 2).

3. خود این عدد اول است. حالا همه مضرب‌های آن (4، 6، 8، ...) را از لیست خط بزنید.

4. به سراغ کوچک‌ترین عدد باقی‌مانده بعدی بروید (حالا 3).

5. دوباره همین کار را تکرار کنید: 3 را نگه دارید و همه مضرب‌هایش (6، 9، 12، ...) را حذف کنید.

6. این فرآیند را ادامه دهید تا به ریشه مربع عدد هدف (اینجا √100 = 10) برسید. پس از بررسی اعداد تا 10، تمام اعداد باقی‌مانده در لیست، اول هستند.

نکات کلیدی و هوشمندانه

• نیازی نیست مضرب‌های همه اعداد را حذف کنید. فقط تا √n کافیه، چون اگر عددی مثل 97 اول باشد، هیچ مضرب کوچک‌تری از اعداد کمتر از √97 آن را حذف نکرده است.
• عدد 2 تنها عدد اول زوج است؛ بقیه اعداد اول فرد هستند. این باعث می‌شود در پیاده‌سازی‌های بهینه، اعداد زوج را از ابتدا کنار بگذاریم و سرعت دو برابر شود.
• پیچیدگی زمانی این الگوریتم O(n log log n) است که برای پیدا کردن اعداد اول تا اعداد بسیار بزرگ (مثل 10^9) همچنان بسیار کارآمد محسوب می‌شود.
• در نسخه‌های مدرن، به جای خط زدن، از یک آرایه بولی استفاده می‌کنیم: ابتدا همه را true (اول فرض می‌کنیم) و سپس مضرب‌ها را false می‌کنیم.
• یکی از کاربردهای جالب آن در رمزنگاری است؛ اعداد اول بزرگ پایه بسیاری از الگوریتم‌های امنیتی مدرن هستند و غربال راهی سریع برای تولید لیست اعداد اول در محدوده‌های متوسط فراهم می‌کند.

این روش نه تنها زیبا و ساده است، بلکه نشان می‌دهد چگونه یک ایده چند هزار ساله هنوز در قلب محاسبات مدرن می‌تپد. هر بار که غربال را اجرا می‌کنید، انگار در حال بازسازی همان لحظه الهام اراتوستن هستید – لحظه‌ای که ریاضیات با سادگی، قدرت خود را نشان داد.

اگر به فیلم آموزشی نکاه مهم در الگوریتم غربال اعداد نیازمند بودید, زوی همین مطلب ضربه بزنید.