بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 6: تعیین عددهای اول Finding Primes

با روش غربال، عددهای اول یک فهرست را پیدا می‌کنیم: ۱ را خط می‌زنیم و بعد مضرب‌های ۲، ۳، ۵، … را. برای این‌که بفهمیم یک عدد اول است یا نه، آن را فقط بر عددهای اول تقسیم می‌کنیم و وقتی مربع عدد اولِ بعدی از خود عدد بیشتر شد، دست می‌کشیم.

در این جلسه یاد می‌گیری

درس

آزمایش تقسیم. آیا ۱۸۷ اول است؟ آن را یکی‌یکی بر ۲، ۳، ۵، ۷، … تقسیم کن و ببین کجا بخش‌پذیر می‌شود. بعد n را ۱۹۷ کن: این بار هیچ تقسیمی بی‌باقی‌مانده نیست. حواست به ⁦d × d⁩ باشد: همین که از n بیشتر شد، کار تمام است.

غربال. عددهای ۱ تا ۶۰ را بنویس و ۱ را خط بزن. ۲ را دور بزن و همه‌ی مضرب‌هایش (۴، ۶، ۸، …) را خط بزن. اولین عدد خط‌نخورده، ۳، را دور بزن و مضرب‌هایش را خط بزن؛ بعد ۵ و بعد ۷. مضرب‌های ۴ یا ۶ را لازم نیست خط بزنی: قبلاً به خاطر ۲ خط خورده‌اند. بعد از ۷ نوبت ۱۱ است، ولی ⁦۱۱ × ۱۱ = ۱۲۱⁩ از ۶۰ بیشتر است؛ پس همه‌ی عددهای خط‌نخورده اول‌اند.

غربال به شکل فلوچارت. قدم‌های غربال برای هر n یک الگوریتم است. از ⁦p = ۲⁩ شروع کن. تا وقتی ⁦p × p⁩ از n بیشتر نشده، مضرب‌های p را خط بزن و p را اولین عدد خط‌نخورده‌ی بعدی بگذار. وقتی ⁦p × p > n⁩ شد، کار تمام است و هر عددی که مانده اول است.

یک عدد را آزمایش کن. آیا ۱۵۷ اول است؟ بر عددهای اول ۲، ۳، ۵، ۷ و ۱۱ تقسیم کن؛ هیچ‌کدام بی‌باقی‌مانده نیست. عدد اول بعدی ۱۳ است و ⁦۱۳ × ۱۳ = ۱۶۹⁩ از ۱۵۷ بیشتر است، پس دست بکش: ۱۵۷ اول است. چرا کافی است؟ اگر ⁦۱۵۷ = a × b⁩ بود و هر دو از ۱۲ بزرگ‌تر بودند، ⁦a × b⁩ دست‌کم ⁦۱۳ × ۱۳ = ۱۶۹⁩ می‌شد. تقسیم بر ۴ یا ۹ هم لازم نیست: اگر ۹ عدد را می‌شمرد، ۳ هم می‌شمرد.

اشتباه رایج: زود دست کشیدن. «۱۶۹ را بر ۲، ۳، ۵، ۷ و ۱۱ تقسیم کردم و بخش‌پذیر نبود، پس اول است.» ولی ⁦۱۳ × ۱۳ = ۱۶۹⁩ هنوز از ۱۶۹ بیشتر نیست، پس ۱۳ را هم باید امتحان کنی: ⁦۱۶۹ = ۱۳ × ۱۳⁩. قاعده: تا وقتی ⁦p × p⁩ کوچک‌تر یا مساوی عدد است، ادامه بده.

با پایتون (اختیاری): غربال با یک لیست درست و غلط: True یعنی خط خورده. حلقه وقتی p * p از n بیشتر شد می‌ایستد.

n = 60
crossed = [False] * (n + 1)
p = 2
while p * p <= n:
    if not crossed[p]:
        for m in range(p * p, n + 1, p):
            crossed[m] = True
    p = p + 1
print([k for k in range(2, n + 1) if not crossed[k]])

مثال‌های این جلسه

چالش‌ها

  1. Primes from 61 to 80 (آسان)
  2. Where to Stop (آسان)
  3. Is 209 Prime? (متوسط)
  4. The Sieve, Step by Step (متوسط)
  5. Three-Digit Numbers (سخت)
  6. Sara's Test (سخت)

بیشتر بخوان

← جلسه‌ی 5: یادآوری عددهای اول جلسه‌ی 7: چندضلعی‌ها و تقارن →