جلسهی 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]])مثالهای این جلسه
چالشها
- Divisors of 18 (آسان)
- Which One Is Prime? (آسان)
- Primes from 30 to 60 (متوسط)
- Prime, Composite or Neither (متوسط)
- How Many Below 50? (سخت)
- Two Primes Added (سخت)
بیشتر بخوان
← جلسهی 16: شکلهای مساوی (همنهشت) جلسهی 18: شمارندهی اول →