Sonni tub ko’paytuvchilarga ajratish

“Mathematics is the queen of the sciences and number theory is the queen of mathematics.” — Carl Friedrich Gauss

II qism. Sonlar nazariyasi. 4-dars

Oldingi darsda sizlar bilan N gacha bo’lgan tub sonlarni topishni ko’rib chiqqandik. Bugungi darsda sonni tub ko’paytuvchilarga ajratishni ko’rib chiqamiz.

N sonini tub ko’paytuvchilarga ajratish algoritmi:

  1. N ning eng kichik p tub bo’luvchisini topamiz.
  2. N p ga necha marta qoldiqsiz bo’linsa, shuncha marta bo’lib chiqamiz va har safar p ni saqlab boramiz.
  3. N ning keyingi eng kichik tub bo’luvchisini topamiz va 2-qadamni takrorlaymiz.
  4. 2- va 3-qadamlarni N birga teng bo’lib qolmaguncha davom ettiramiz. p larni saqlab borgan massivimiz bizga N ning barcha tub ko’paytuvchilarini beradi.

Eslatma: Yuqoridagi algoritmning qadamlarida faqat tub sonlarni tekshirish shart emas. Masalan, 100 sonimizni 2 marta 2 ga bo’lganimizdan keyin 25 hosil bo’ladi va u endi 4, 6, 8, … va hokazo sonlarning hech qaysisiga qoldiqsiz bo’linmaydi.

Algoritm qanday ishlaydi

Misol uchun, N = 2633400 bo’lsin

  1. 2 ga qoldiqsiz bo’linar ekan uni 2 ga bo’lishda davom etamiz. Bo’linishlar soni 3 ta bo’ladi. Bunda N = 329175 va massivimiz [2, 2, 2] ko’rinishga keladi.
  2. 3 soni uchun ham yuqoridagi ish 2 marta takrorlanadi. N = 36575 va massivimiz [2, 2, 2, 3, 3] bo’ladi.
  3. N = 36575 soni 4 ga bo’linmaydi, demak davom etamiz.
  4. 5 ga bo’lib chiqilgandan keyin N = 1463 va massiv [2, 2, 2, 3, 3, 5, 5]
  5. 6 ga bo’linmaydi 7 ga o’tiladi.
  6. Shu tariqa davom etib yakunda N = 1.
    Javob esa [2, 2, 2, 3, 3, 5, 5, 7, 11, 19] ko’rinishga keladi.

Algoritm implementatsiyasi videosiga o’tishdan oldin uni mustaqil o’zingiz ishlab ko’ring.

Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing.

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan