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

جلسه‌ی 17: عدد اول Prime Numbers

شمارنده‌های یک عدد، عددهایی‌اند که آن را بی‌باقی‌مانده تقسیم می‌کنند. عدد اول دقیقاً دو شمارنده دارد: ۱ و خودش. با غربال اراتستن عددهای اول تا ۱۰۰ را پیدا می‌کنیم.

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

درس

غربال اراتستن. دانشمندی یونانی بیش از دو هزار سال پیش این روش را پیدا کرد. روی ۲ بزن: ۲ اول است و همه‌ی مضرب‌هایش خط می‌خورند. بعد کوچک‌ترین عدد خط‌نخورده ⁦(۳)⁩ را بزن، بعد ۵ و ۷. ببین چرا بعد از ۷ کار تمام است.

شمارنده. a شمارنده‌ی b است اگر b بر a بخش‌پذیر باشد. شمارنده‌های ۱۲ را جفت‌جفت پیدا کن: ⁦۱ × ۱۲⁩، ⁦۲ × ۶⁩، ⁦۳ × ۴⁩؛ پس ۱، ۲، ۳، ۴، ۶ و ۱۲. کوچک‌ترین شمارنده‌ی هر عدد ۱ است و بزرگ‌ترینش خود آن عدد.

عدد اول دقیقاً دو شمارنده دارد: ۱ و خودش؛ مثل ۲، ۳، ۵، ۷، ۱۱، ۱۳. عددی که بیشتر از دو شمارنده دارد مرکب است، مثل ۹ (۱، ۳، ۹). عدد ۱ فقط یک شمارنده دارد، پس نه اول است نه مرکب. ۲ تنها عدد اول زوج است.

چرا غربال تا ۷ کافی است؟ هر عدد مرکب تا ۱۰۰ یک شمارنده‌ی اول کوچک‌تر یا مساوی ۱۰ دارد، چون ⁦۱۱ × ۱۱ = ۱۲۱⁩ از ۱۰۰ بیشتر است. پس با خط زدن مضرب‌های ۲، ۳، ۵ و ۷ همه‌ی مرکب‌ها رفته‌اند.
اشتباه رایج: «هر عدد فرد اول است.» نه: ۹، ۱۵، ۲۱، ۲۷ و حتی ⁦۹۱ (= ۷ × ۱۳)⁩ مرکب‌اند.

با پایتون (اختیاری): همان غربال، با یک لیست درست و غلط: True یعنی هنوز خط نخورده.

n = 100
alive = [True] * (n + 1)
alive[0] = alive[1] = False
for p in range(2, 11):
    if alive[p]:
        for m in range(2 * p, n + 1, p):
            alive[m] = False
print([k for k in range(n + 1) if alive[k]])

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

چالش‌ها

  1. Divisors of 18 (آسان)
  2. Which One Is Prime? (آسان)
  3. Primes from 30 to 60 (متوسط)
  4. Prime, Composite or Neither (متوسط)
  5. How Many Below 50? (سخت)
  6. Two Primes Added (سخت)

بیشتر بخوان

← جلسه‌ی 16: شکل‌های مساوی (هم‌نهشت) جلسه‌ی 18: شمارنده‌ی اول →