روش غربال: یک راه‌حل هوشمند برای یافتن گنج‌های پنهان اعداد
اعداد اول چه هستند و چرا مهم‌اند؟
اعداد اول، اعداد طبیعی بزرگتر از یک هستند که تنها بر یک و خودشان بخش‌پذیر باشند. به زبان ساده، این اعداد را نمی‌توان به صورت حاصل‌ضرب دو عدد طبیعی کوچکتر ساخت. برای مثال، عدد 7 یک عدد اول است، زیرا فقط می‌توان آن را به صورت 1 × 7 نوشت. اما عدد 8 اول نیست، چون به صورت 2 × 4 نیز نوشته می‌شود.
این اعداد در بسیاری از جنبه‌های زندگی کاربرد دارند. امنیت اطلاعات در تلفن همراه، رمزگذاری کارت‌های بانکی و حتی چیدمان برخی حشرات در طبیعت بر پایه اعداد اول استوار است. پیدا کردن این اعداد مانند پیدا کردن الماس در یک معدن است و روش غربال، ابزار اصلی این کار است.
غربال اراتوستن، قدم به قدم
اراتوستن، دانشمند یونانی، بیش از ۲۲۰۰ سال پیش این روش را ابداع کرد. فرض کنید می‌خواهیم تمام اعداد اول بین 1 تا 30 را پیدا کنیم. مراحل کار به شرح زیر است:
| گام | عملیات | نتیجه (اعداد حذف‌شده) | توضیح |
|---|---|---|---|
| ۱ | حذف عدد ۱ | 1 | عدد ۱ اول نیست. |
| ۲ | عدد ۲ را اول می‌دانیم و مضرب‌های آن را حذف می‌کنیم. | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 | این اعداد همگی بر ۲ بخش‌پذیرند. |
| ۳ | عدد ۳ را اول می‌دانیم و مضرب‌های باقی‌مانده آن را حذف می‌کنیم. | 9, 15, 21, 27 | اعدادی مانند ۹ و ۱۵ که بر ۳ بخش‌پذیرند ولی هنوز خط نخورده‌اند. |
| ۴ | عدد ۵ را اول می‌دانیم و مضرب‌های باقی‌مانده آن را حذف می‌کنیم. | 25 | عدد ۲۵ مضرب ۵ است که هنوز حذف نشده بود. |
| ۵ | توقف الگوریتم | - | وقتی به عدد اول بعدی (۷) می‌رسیم، مربع آن (49) از 30 بزرگتر است، پس کار تمام است. |
پس از اتمام این مراحل، اعداد باقی‌مانده در لیست که خط نخورده‌اند، همگی اول هستند: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
یک بازی گروهی با روش غربال
می‌توانید این روش را به صورت یک بازی در کلاس انجام دهید. از ۳۰ دانش‌آموز بخواهید هر کدام یک کارت با شماره‌های ۱ تا ۳۰ در دست بگیرند. سپس به ترتیب از آن‌ها بخواهید:
- دانش‌آموز شماره ۱ بنشیند (حذف شود).
- دانش‌آموز شماره ۲ بایستد و تمام کسانی که شماره‌های مضرب ۲ دارند (۴، ۶، ۸ و ...) بنشینند.
- سپس دانش‌آموز شماره ۳ بایستد و تمام مضرب‌های باقی‌مانده ۳ (۹، ۱۵، ۲۱ و ...) بنشینند.
- این روند ادامه می‌یابد. در پایان، تنها کسانی ایستاده‌اند که شماره‌های آن‌ها عدد اول است!
این بازی به درک شهودی و ملموس روش غربال کمک زیادی می‌کند.
اشتباهات رایج و پرسش‌های مهم
پاسخ: چون مضرب‌های یک عدد مرکب، قبلاً توسط مقسوم‌علیه‌های اول آن عدد حذف شده‌اند. برای مثال، مضرب‌های عدد مرکب 4، در واقع همان مضرب‌های عدد اول 2 هستند که در مرحله اول حذف شده‌اند. بنابراین، کار تکراری انجام نمی‌دهیم.
پاسخ: بله، عدد 2 تنها عدد زوج اول است. این یک استثنای جالب در دنیای اعداد اول به حساب می‌آید. شرط عدد اول این است که تنها بر یک و خودش بخش‌پذیر باشد و عدد 2 این شرط را دارد.
پاسخ: خیر، روش غربال اراتوستن برای اعداد بسیار بزرگ (مثلاً با ۱۰۰ رقم) به دلیل نیاز به حافظه و زمان محاسباتی بسیار زیاد، عملی نیست. ریاضیدانان برای پیدا کردن اعداد اول بسیار بزرگ از روش‌های پیشرفته‌تری استفاده می‌کنند.
پاورقی
1روش غربال (Sieve Method): به روش‌هایی در نظریه اعداد گفته می‌شود که با حذف کردن اعداد مرکب، اعداد اول را جدا می‌کنند.
2اراتوستن (Eratosthenes): دانشمند یونانی سده سوم پیش از میلاد که ریاضیدان، جغرافیدان و مدیر کتابخانه اسکندریه بود. او محیط زمین را نیز با دقت خوبی اندازه‌گیری کرد.
3عدد اول (Prime Number): عدد طبیعی بزرگتر از ۱ که جز یک و خودش مقسوم‌علیه دیگری نداشته باشد.
4عدد مرکب (Composite Number): عدد طبیعی بزرگتر از ۱ که عدد اول نباشد.
5مضرب (Multiple): حاصل‌ضرب یک عدد در یک عدد طبیعی. مثلاً مضرب‌های ۳ عبارت‌اند از: 3, 6, 9, 12, ...
