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

آیا ۹۱ عدد اول است؟ فرد است، پس ۲ شمارنده‌ی آن نیست. مجموع رقم‌هایش ۱۰ است، پس ۳ هم شمارنده‌اش نیست. به نظر اول می‌آید. اما ⁦۹۱ = ۷ × ۱۳⁩، پس مرکب است. امتحان کردن عددها یکی‌یکی کند است و آدم راحت اشتباه می‌کند. آیا راه بهتری برای پیدا کردن همه‌ی عددهای اول تا ۱۰۰ هست؟

مردی که زمین را اندازه گرفت

حدود ۲٬۲۰۰ سال پیش دانشمندی یونانی به نام اراتستن در اسکندریه‌ی مصر زندگی می‌کرد. او حدود سال ۲۷۶ پیش از میلاد در شهر کورنه، در لیبی امروزی، به دنیا آمده بود و سرپرست کتابخانه‌ی بزرگ اسکندریه بود. اراتستن را بیشتر به این خاطر می‌شناسند که با کمک سایه‌ها اندازه‌ی زمین را حساب کرد. اما روشی هم برای پیدا کردن عددهای اول از او به یادگار مانده است که به آن غربال اراتستن (sieve of Eratosthenes) می‌گویند. غربال (sieve) وسیله‌ای سوراخ‌سوراخ در آشپزخانه است: آرد را در آن می‌ریزید، آرد پایین می‌ریزد و کلوخه‌ها در غربال می‌مانند. در غربال اراتستن عددهای مرکب پایین می‌ریزند و عددهای اول باقی می‌مانند.

غربال چطور کار می‌کند

عددهای ۱ تا ۱۰۰ را در یک جدول بنویسید، هر ردیف ده عدد. بعد:

1. ۱ را خط بزنید. ۱ عدد اول نیست.
2. دور ۲، نخستین عدد اول، دایره بکشید. همه‌ی مضرب‌های دیگر ۲ را خط بزنید: ۴، ۶، ۸، ۱۰ و همین‌طور تا آخر. همه‌ی آن‌ها ۲ را شمارنده دارند، پس هیچ‌کدام اول نیستند.
3. نخستین عددی که خط نخورده ۳ است. دورش دایره بکشید و مضرب‌های ۳ را خط بزنید: ۶، ۹، ۱۲ و بقیه (بعضی از آن‌ها از قبل خط خورده‌اند).
4. ۴ خط خورده است. عدد بعدیِ باقی‌مانده ۵ است: دورش دایره بکشید و مضرب‌هایش را خط بزنید.
5. بعد نوبت ۷ است: دورش دایره بکشید و ۱۴، ۲۱، ۲۸ و بقیه تا ۹۱ و ۹۸ را خط بزنید.

هر عددی که خط می‌زنید مضربِ عددی کوچک‌تر است، پس شمارنده‌ای دارد که نه ۱ است و نه خودش. هر عددی که هیچ‌وقت خط نمی‌خورد، جز ۱ هیچ شمارنده‌ی کوچک‌تری ندارد، پس اول است.

کِی می‌شود دست نگه داشت؟

عدد اول بعدی ۱۱ است. مضرب‌هایش ۲۲، ۳۳، ۴۴ و همین‌طور تا ۹۹ هستند. اما هر کدام از این‌ها ۱۱ ضرب در عددی کوچک‌تر از ۱۱ است، مثلاً ⁦۲۲ = ۱۱ × ۲⁩ و ⁦۳۳ = ۱۱ × ۳⁩. پس وقتی با ۲، ۳، ۵ یا ۷ غربال می‌کردیم، این‌ها خط خورده بودند. نخستین مضرب ۱۱ که تازه است ⁦۱۱ × ۱۱ = ۱۲۱⁩ است که از ۱۰۰ بزرگ‌تر است.

پس بعد از ۷ کار تمام است. هر عددی که هنوز سر جایش مانده عدد اول است. دور همه‌ی آن‌ها دایره بکشید: تا ۱۰۰، ۲۵ عدد اول هست.

به عددهای دایره‌دار نگاه کنید. جز ۲ و ۵، رقم یکان همه‌شان ۱، ۳، ۷ یا ۹ است. هیچ الگوی ساده‌ای ندارند، و این یکی از معماهای بزرگ ریاضی است.

در خانه امتحان کنید

1. عددهای ۱ تا ۵۰ را در پنج ردیف ده‌تایی بنویسید و با ۲، ۳، ۵ و ۷ غربالشان کنید. چند عدد اول باقی می‌ماند؟
2. چرا برای عددهای تا ۴۸ لازم نیست با ۷ غربال کنید؟

جواب‌ها: ۱. ۱۵ عدد اول (۲، ۳، ۵، ۷، ۱۱، ۱۳، ۱۷، ۱۹، ۲۳، ۲۹، ۳۱، ۳۷، ۴۱، ۴۳ و ۴۷)؛ ۲. نخستین مضرب تازه‌ی ۷ عدد ⁦۷ × ۷ = ۴۹⁩ است.

واژه‌های این درس

• غربال (sieve) - وسیله‌ای سوراخ‌دار که چیزهای ریز را رد می‌کند و بقیه را نگه می‌دارد؛ در ریاضی، خط زدن عددها تا آن‌هایی که می‌خواهیم باقی بمانند
• غربال اراتستن (sieve of Eratosthenes) - پیدا کردن عددهای اول با خط زدن مضرب‌های هر عدد اول، یکی پس از دیگری

ایده‌ی اصلی

مضرب‌های ۲، ۳، ۵ و ۷ را خط بزنید؛ عددهایی که تا ۱۰۰ باقی می‌مانند دقیقاً عددهای اول‌اند، یعنی ۲۵ عدد. وقتی حاصل‌ضرب یک عدد اول در خودش از آخر جدول بزرگ‌تر شد، می‌توانید دست نگه دارید.