34-dars: Sonlar nazariyasi

5-darajaOlimpiada — musobaqa mahorati33–40 darslar

HayotdaBayram

48 ta shar va 18 ta lenta bor. Ularni bir xil to’plamlarga bo’lish kerak, hech narsa ortib qolmasin. Eng ko’pi bilan nechta to’plam chiqadi? Javob — 6, va uni topish uchun ikki mingdan ortiq yildan beri o’zgarmagan usul ishlatiladi.

Bu darsdan keyin siz

• EKUB ni Yevklid algoritmi bilan hisoblaysiz
• modul arifmetikasida ishlaysiz va bo’lishni teskari element bilan almashtirasiz
• Eratosfen elagini yozasiz va nega u tez ekanini tushuntirasiz

Avval qo’lda

Avval qo‘lda

~6 daqiqa·yakka·Katakli qog'oz

Katakli qog’ozga 2 dan 50 gacha sonlarni yozing. Endi elakni qo’lda o’tkazing.

Ikkini aylanaga oling, so’ng uning karralilarini o’chiring — lekin 2 × 2 = 4 dan boshlang. Keyin uchni aylanaga oling va 9 dan boshlab o’chiring. Beshni — 25 dan. Yettini — 49 dan. Endi to’xtang.

Nimani sezishingiz kerak

Nega to’xtadingiz: keyingi son 11, uning kvadrati esa 121 — 50 dan katta. Demak o’chiradigan hech narsa qolmadi. Qolgan aylanasiz sonlarning hammasi ham tub.

Kompyuter yopiq. Bu mashq tugamaguncha kod ochilmaydi.

EKUB va Yevklid

EKUBGCD

Ikki sonni qoldiqsiz bo’ladigan eng katta son. Yevklid algoritmi uni bo’lish qoldiqlari orqali topadi.

Butun algoritm bir qatorga sig’adi: EKUB(a, b) = EKUB(b, a mod b), va b = 0 bo’lganda javob a.

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1from math import gcd2def ekub(a, b):3  while b:4      a, b = b, a % b5  return a6print(ekub(48, 18), ekub(17, 5), ekub(0, 7))7print(gcd(48, 18) == ekub(48, 18))

Sizning bashoratingizTekshirish

Javobni ko'rish

6 1 7
True

Har qadamda sonlar keskin kichrayadi: qadamlar soni log dan oshmaydi. math.gcd tayyor holda bor, lekin qo'lda yozishni bilish kerak.

EKUK esa EKUB orqali chiqadi: a * b // EKUB(a, b). Avval bo’lib, keyin ko’paytirish ma’qul — aks holda oraliq son juda katta bo’lib ketishi mumkin.

Modul arifmetikasi

Javob katta bo’lganda shart odatda 10⁹ + 7 ga bo’lgandagi qoldiqni so’raydi. Qo’shish, ayirish va ko’paytirish muammosiz: qoldiqni istalgan paytda olish mumkin.

▲Bu yerda xato qilishadi

Bo’lish esa ishlamaydi. (a / b) mod p degan narsa yo’q. O’rniga b ning teskari elementi topiladi: shunday x ki, b · x ≡ 1. p tub bo’lsa Ferma kichik teoremasi javob beradi: x = b^(p−2).

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1MOD = 10**9 + 72print(pow(2, 100, MOD) == (2 ** 100) % MOD)3teskari = pow(3, MOD - 2, MOD)4print(3 * teskari % MOD)

Sizning bashoratingizTekshirish

Javobni ko'rish

True
1

pow(a, b, m) darajani modul ostida tez hisoblaydi — u sonni to'liq yasamaydi. Uchning teskarisiga uchni ko'paytirsak bir chiqadi, ta'rifi shu.

Sekin yechim

Masala: n gacha nechta tub son bor? Har sonni alohida tekshiramiz.

sekin.pyNusxalash

1def tubmi(x):2  if x < 2:3      return False4  d = 25  while d * d <= x:6      if x % d == 0:7          return False8      d += 19  return True10print(sum(1 for x in range(2, 31) if tubmi(x)))

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1def tubmi(x):2  if x < 2:3      return False4  d = 25  while d * d <= x:6      if x % d == 0:7          return False8      d += 19  return True10print(sum(1 for x in range(2, 31) if tubmi(x)))

Sizning bashoratingizTekshirish

Javobni ko'rish

10

30 gacha o'nta tub son bor. Bitta sonni tekshirish sqrt(x) amal, hammasi uchun esa taxminan n·sqrt(n).

Sig‘adimi?

Bir soniyada taxminan 10⁸ oddiy amal bajariladi.

Yechim	n = 1 000	n = 200 000	n = 10⁶
Har sonni tekshirishn^2	10⁶sig‘adi	10¹⁰sig‘maydi	10¹²sig‘maydi
Eratosfen elagin	1 000sig‘adi	200 000sig‘adi	10⁶sig‘adi

Yashil — yechim o‘tadi. Sariq — chegarada, konstanta va til muhim bo‘lib qoladi. Qizil — bu yechim bilan bormaydi, boshqasini qidiring.

Jadval qo’pol (n·sqrt(n) aniq n² emas), lekin nisbat to’g’ri: n = 10⁶ da birinchi usul bir necha daqiqa, ikkinchisi bir soniyadan kam.

Tez yechim

Elak sonlarni tekshirmaydi — u tub sonlarning karralilarini o’chiradi.

tez.pyNusxalash

1n = 302tub = [True] * (n + 1)3tub[0] = tub[1] = False4p = 25while p * p <= n:6  if tub[p]:7      for k in range(p * p, n + 1, p):8          tub[k] = False9  p += 110print([x for x in range(n + 1) if tub[x]])

?Avval o'ylang: bu kod nima chiqaradi? Ishga tushirishdan oldin yozing.

Bashorat qilingNusxalash

1n = 302tub = [True] * (n + 1)3tub[0] = tub[1] = False4p = 25while p * p <= n:6  if tub[p]:7      for k in range(p * p, n + 1, p):8          tub[k] = False9  p += 110print([x for x in range(n + 1) if tub[x]])

Sizning bashoratingizTekshirish

Javobni ko'rish

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Ikki nozik joy beshinchi va yettinchi qatorlarda: tashqi sikl sqrt(n) gacha, ichki sikl esa p·p dan boshlanadi.

Nega p · p dan: 2p, 3p va boshqa kichik karralilar allaqachon o’chirilgan — ularning kichikroq tub bo’luvchisi bor edi.

Ish hajmi n/2 + n/3 + n/5 + ..., bu yig’indi n log log n ga teng — amalda deyarli chiziqli.

Sinab ko’r

Vizualda elak ishlaydi. Hech qaysi son alohida tekshirilmasligini kuzating.

Eratosfen elagi

Yashil — tub, kulrang — o'chirilgan. Hech bir son alohida tekshirilmaydi.

Har tub sonning karralilari p*p dan boshlab o'chiriladi; qolganlari tub bo'lib chiqadi.

Algoritmning har qadami quyidagi ro‘yxatda matn sifatida ham berilgan — vizual faqat shu qadamlarni chizadi, yangi ma’lumot qo‘shmaydi.

1. 2 dan 25 gacha sonlar. Elak hech qaysi sonni TEKSHIRMAYDI — u faqat karralilarni o'chiradi.
2. 2 tub. Uning karralilari 2 x 2 = 4 dan boshlab o'chiriladi: 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24. Kichikroq karralilar allaqachon o'chgan.
3. 3 tub. Uning karralilari 3 x 3 = 9 dan boshlab o'chiriladi: 9, 15, 21. Kichikroq karralilar allaqachon o'chgan.
4. 5 tub. Uning karralilari 5 x 5 = 25 dan boshlab o'chiriladi: 25. Kichikroq karralilar allaqachon o'chgan.
5. Qolganlarining hammasi tub: 9 ta. Tashqi sikl faqat 25 ning kvadrat ildizigacha yurdi — undan katta tub son hech narsani o'chira olmaydi.

2+

234567

8+

8910111213

14+

141516171819

20+

202122232425

2 dan 25 gacha sonlar. Elak hech qaysi sonni TEKSHIRMAYDI — u faqat karralilarni o'chiradi.

O'chirish0

OrqagaO‘ynatishOldinga1/5Qayta boshlash

Xatoni toping

▲Tuzoq — xatoni toping

34 / 40

MasalaKatta sonlarni modul ostida bo'ling: (a * b) / c mod p.

Taklif qilingan yechim

1. 1p = 10⁹ + 7 tub son.
2. 2a va b ni ko‘paytirib, qoldiq olamiz.
3. 3Natijani c ga bo‘lib, yana qoldiq olamiz.
4. 4Javob tayyor.

Bu javobning 3-qismi noto'g'ri. Modul ostida bo'lish yo'q. (x // c) % p umuman boshqa son beradi: qoldiq olingandan keyin x ning c ga bo'linishi ham buzilgan bo'ladi. To'g'risi: c ning teskari elementiga ko'paytirish — x * pow(c, p - 2, p) % p.

Javobning qaysi qismi noto'g'ri? Bosib belgilang.

Javobni ko'rsatish

O’zingizni sinang

1Yevklid algoritmi nechta qadam qiladi?

Javobni ko'rish

Logarifmik: har qadamda sonlar keskin kichrayadi. Million atrofidagi sonlar uchun ham bir necha o’nlab qadam yetadi.

2Modul ostida nima ishlaydi, nima ishlamaydi?

Javobni ko'rish

Qo’shish, ayirish va ko’paytirish ishlaydi. Bo’lish ishlamaydi — uning o’rniga teskari element ishlatiladi.

3Teskari element qanday topiladi?

Javobni ko'rish

Modul tub bo’lsa, Ferma kichik teoremasi bo’yicha b^(p−2). Python’da pow(b, p - 2, p).

4Elakda ichki sikl nega p · p dan boshlanadi?

Javobni ko'rish

Kichikroq karralilar allaqachon o’chirilgan: ularning p dan kichik tub bo’luvchisi bor edi.

5Tashqi sikl qayergacha yuradi va nega?

Javobni ko'rish

sqrt(n) gacha. Undan katta p uchun p · p allaqachon n dan oshgan, demak o’chiradigan hech narsa qolmagan.

Masalalar

Masalalar

3 ta

• Counting DivisorsCSES 1713o'rta

  Elakning boshqa ko‘rinishi: har son uchun uning karralilariga bittadan qo‘shib chiqing.

• ExponentiationCSES 1095oson

  Python‘da pow(a, b, m) tayyor. Lekin uni qo‘lda ham yozib ko‘ring — C++ da kerak bo‘ladi.

• Common DivisorsCSES 1081o'rta

  Har mumkin bo‘lgan bo‘luvchi uchun uning karralilari nechtaligini sanang — elak uslubida.

Lokal mashq: mashqlar/34-elak/ — masala matni, testlar va tekshir.py. Avval sekin.py ni o‘zingiz yozing, keyin tayyorini oching.

Topshiriq

Topshiriq — darajangizni tanlang

Asos5–7-sinfMustahkam8–9-sinfChuqur10–11-sinf

Asos · 5–7-sinf — Vizual va aniq ko'rsatmali

50 gacha elakni qog’ozda o’tkazing va tub sonlarni sanang. Keyin har qadamda nechta son o’chirilganini yozing — yig’indi qanchaga teng bo’ldi?

Mustahkam · 8–9-sinf — Matnli masala, o'zingiz tuzasiz

34-elak masalasini yeching. Ikkala yechimni n = 200000 da o’lchang va nisbatni yozing.

Chuqur · 10–11-sinf — Algoritmik, chegara holatlari bilan

Elakni o’zgartiring: har son uchun uning eng kichik tub bo’luvchisini saqlang. Shu jadval bilan istalgan sonni tub ko’paytuvchilarga log n da ajratish mumkin — buni yozing va sinab ko’ring.

Darsni belgilash uchun JavaScript kerak. Bu progressni saqlash uchun ishlatiladi — darslikning o'zi JavaScript'siz ham to'liq o'qiladi.

Darsni tugatdim