Urganch davlat universiteti axborot texnologiyalari kafedrasi

1.2 Algoritmlar murakkabligi bilan tanishuv. 

Murakkablik  tushunchasi  bilan  tanishish  uchun  natural  sonlarni  qayta  ishlash  bilan 

bog‘langan ikkita fundamental masalani qarab chiqamiz. Ularni yechmasdan, masalan, bitta ham 

zamonaviy shifrlash sistemasi o‘tib ketolmaydi. 

1.4-masala. Natural son oddiy hisoblanadimi yoki yo‘qligi aniqlansin. 

Masala  tahlili  va  yechimi.  n,  n>1,  son  oddiy  son  deyiladi,  agarda  ikkita  musbat  1  va  n 

bo‘luvchilarga  ega  bo‘lsa.  Aks  holda  tarkibiy  deb  ataladi.  2  dan  katta  har  qanday  juft  son 

tarkibiy,  2  esa  oddiy  hisoblanadi.  n>2  bo‘lgan  toq  n  soni  2,3,…,n-1  sonlaridan  bittasiga  ham 

qoldiqsiz  bo‘linmasa  oddiy  hisoblanadi.  Shunday  qilib,  2  dan  n-1  gacha  bo‘lgan  n  navbatdagi 

bo‘luvchiga  k  bo‘luvchiga  bo‘linadigan  barcha  k  larni  tanlash  kerak.  Biroq  hisoblashlarni 

tezlashtirish mumkin. Agar n tarkibiy bo‘lsa, u holda n=k

1

k

2

, bu yerda k

1

 va k

2

 ham birdan katta, 

ulardan  kichiklari  √n  dan  katta  emas.  Shuning  uchun  n  soni  oddiy  son  ekanligini  tekshirish 

uchun  uni  2 dan  [√n]  gacha  bo‘linmasligini  tekshirish  zarur.  Bu  bo‘linuvchanliklarni  tekshirish 

miqdorini taxminan √n marta kamaytirish imkonini beradi. Bo‘linuvchanlikni toq k ga tekshirish 

ham yetarlidir. Ushbu massivlar isPrime (prime-oddiy) funksiyasida amalga oshirilgan: