Bir qator asosiy omillarga ajratish nimani anglatadi?

Bosh faktorizatsiya algoritmi

Raqamni asosiy omillarga ajratish vazifasini muvaffaqiyatli hal qilish uchun siz maqoladagi asosiy va aralash raqamlardagi ma'lumotlarni juda yaxshi bilishingiz kerak.

Musbat butun sonni birlikdan kattaroq qismlarga ajratish jarayonining mohiyati arifmetikaning asosiy teoremasi isbotidan yaqqol ko'rinib turibdi. Ma'nosi p eng kichik asosiy bo'linuvchini p-ni izchillik bilan topishdir₁, p₂, ..., p_n a, a raqamlari₁, a₂, ..., a_n-1 , a = p tengliklarning ketma-ketligini olishga imkon beradi₁A₁ qaerda a₁= a: p₁ , a = p₁A₁= p₁P₂A₂ qaerda a₂= a₁: p₂ , ..., a = p₁P₂· ... · b_nA_n qaerda a_n= a_n-1: p_n . Qachon qiladi_n= 1, keyin tenglik a = p₁P₂· ... · b_n bizga a-ni kerakli faktorizatsiya beradi. Bu erda ta'kidlash kerakki, p₁≤p₂≤p₃≤ ... ≤p_n .

Har qadamda eng kichik asosiy bo'linuvchini topish bilan shug'ullanish qoladi va bizda sonni asosiy omillarga ajratish algoritmi bo'ladi. Bosh bo'linuvchilarni topish bizga tub sonlar jadvalini topishda yordam beradi. Z ning eng kichik bo'luvchisini olish uchun qanday foydalanishni ko'rsatamiz.

Biz tub sonlarni ketma-ket tub sonlar jadvalidan olamiz (2, 3, 5, 7, 11 va hokazo) va berilgan z sonini ikkiga bo'lamiz. Z to'liq bo'lingan birinchi tub son uning eng kichik eng katta bo'linuvchisi bo'ladi. Agar z asosiy bo'lsa, uning eng kichik bo'linuvchisi z ning o'zi bo'ladi. Bu erda shuni eslatib o'tish kerakki, agar z tub son bo'lmasa, unda uning eng kichik tub bo'luvchisi sondan oshmaydi, z ning arifmetik kvadrat ildizi qaerda. Shunday qilib, agar tub sonlar orasida z ning bo'linmas qismi mavjud bo'lmasa, unda z tub son ekanligi haqida xulosa qilishimiz mumkin (bu haqida ko'proq ma'lumot olish uchun, bu son tub yoki aralash degan sarlavha ostidagi nazariya bo'limiga qarang).

Misol sifatida biz 87 ning eng kichik asosiy bo'linuvchisini qanday topishni ko'rsatamiz. 2 raqamini oling. 87 ni 2 ga bo'ling, biz 87: 2 = 43 (qolgan 1) ni olamiz (agar kerak bo'lsa, qoidaga bag'ishlangan maqolani va qolgan son bilan butun sonlarni ajratish misollarini ko'ring). Ya'ni 87 ni 2 ga bo'lganda, qoldiq 1 ga teng, shuning uchun 2 87 ga bo'linmaydi. Biz tub sonlar jadvalidan quyidagi tub sonni olamiz, bu 3 raqami. 87 ni 3 ga bo'ling, biz 87: 3 = 29 ni olamiz. Shunday qilib 87 to'liq 3 ga bo'linadi, shuning uchun 3 87 ning eng kichik asosiy bo'linuvchisidir.

E'tibor bering, umumiy holatda, a ning asosiy omillari uchun bizdan kam bo'lmagan songacha tub sonlar jadvali kerak bo'ladi. Biz har qadamda ushbu jadvalga murojaat qilishimiz kerak, shuning uchun uni qo'limizda bo'lishimiz kerak. Masalan, 95 ning asosiy omillariga bo'linish uchun bizga 10 tagacha tub sonlar jadvali kerak (chunki 10 dan oshadi). Va 846 653 sonini kengaytirish uchun 1000 gacha tub sonlar jadvali kerak bo'ladi (chunki ularning soni 1000 dan oshadi).

Endi biz yozib olish uchun etarli ma'lumotga egamiz asosiy faktorizatsiya algoritmi. A sonining parchalanish algoritmi quyidagicha:

• 
  Bosh jadvaldan raqamlarni ketma-ket tartiblash orqali eng kichik tub bo'luvchini p topamiz₁ a raqamlari, shundan keyin biz a ni hisoblaymiz₁= a: p₁ . Agar a₁= 1, u holda a raqami asosiy va bu uning asosiy omillarga kengayishidir. Agar a₁ 1 ga teng bo'lsa, unda a = p ga egamiz₁A₁ va keyingi bosqichga o'ting.
  
• 
  Eng kichik asosiy bo'linuvchini toping p₂ raqamlar a₁ Buni amalga oshirish uchun, p dan boshlanib, bosh jadvaldagi raqamlar bo'yicha tartiblaymiz₁ , shundan keyin biz a ni hisoblaymiz₂= a₁: p₂ . Agar a₂= 1, keyin a = p ni kerakli faktorizatsiyasi₁P₂ . Agar a₂ 1 ga teng bo'lsa, unda a = p ga egamiz₁P₂A₂ va keyingi bosqichga o'ting.
  
• 
  P dan boshlanadigan asosiy jadvaldagi raqamlarni takrorlash₂ , eng kichik asosiy bo'linuvchini toping p₃ raqamlar a₂ , shundan keyin biz a ni hisoblaymiz₃= a₂: p₃ . Agar a₃= 1, keyin a = p ni kerakli faktorizatsiyasi₁P₂P₃ . Agar a₃ 1 ga teng bo'lsa, unda a = p ga egamiz₁P₂P₃A₃ va keyingi bosqichga o'ting.
  
• 
  …
  
• 
  Eng kichik asosiy bo'linuvchini toping p_n raqamlar a_n-1 p dan boshlangan tub sonlar bo'yicha saralash_n-1 shuningdek a_n= a_n-1: p_n , va a_n 1 ga aylanadi. Ushbu qadam algoritmning oxirgi bosqichidir, bu erda biz a: a = p sonining kerakli faktorizatsiyasini olamiz₁P₂· ... · b_n .
  

Raqamni asosiy omillarga ajratish algoritmining har bir bosqichida olingan barcha natijalar quyidagi jadval shaklida aniqlik uchun keltirilgan, unda a, a raqamlari ketma-ket vertikal chiziqning chap tomonidagi ustunga yozilgan.₁, a₂, ..., a_n , va satrning o'ng tomonida p ga mos keladigan eng kam bo'linadigan p₁, p₂, ..., p_n .

Olingan algoritmni sonlarni asosiy omillarga ajratish uchun bir necha misollarni ko'rib chiqishgina qoladi.