1-мавзу. Алгоритмик масалани ечиш асослари 4соат

Бошланиши учун 2 дан n сонигача бутун сонлар кетма-кетликларидан иборат рўйхатни тузамиз, 
кейин ундан биз оддий санларни танлаймиз. Кейин алгоритмнинг биринчи ўтишида 2 сонига 
бўлинадиган барча сонларни, яъни 4, 6 ва ҳ.к. сонларни рўйхатдан ўчириш керак. Кейин рўйхатдан 
навбатдаги сонни танлаш зарур (бу ҳолда бу 3) ва унга бўлинадиган барча сонларни рўйхатдан 
ўчириш керак (алгоритмнинг тавсифланаётган оддий версиясида унча катта бўлмаган янглишиш 
мавжуд, чунки сонлардан айримлари, масалан, 6 рўйхатда бир мартадан ортиқ ўчирилиши керак). 
4 сони учун рўйхат бўйича махсус ўтишни бажариш керак эмас, чунки 4 сони 2 сонига каррали, 
шунинг учун у рўйхатдан биринчи ўтишда ўчирилади. (Бу алгоритмда худди шундай тарзда олдинги 
ўтишларда рўйхатдан ўчирилган қолган барча сонлар учун ҳам ўтишни бажариш керак эмас). 
Рўйхатда қолган ва учинчи қадамда ишлатиладиган навбатдаги сон 5 сони ҳисобланади. 
Алгоритмнинг ишлаши рўйхатда ўчирилиши мумкин бўлган сон қолмагунча давом этади. Алгоритм 
бажарилганидан кейин рўйхатда қолган сонлар оддий сонлар ҳисобланади. 
Юқорида тавсифланган алгоритмнинг ишлатилишига мисол сифатида п = 25 дан ошмайдиган 
одий сонларни қидириш жараёнини кўриб чиқамиз. 
Бизнинг мисолимиз учун рўйхат бўйича кўп сонли ўтишлар талаб қилинмайди, чунки ундан 
кўриб чиқилган ўтишларда барча таркибий сонлар ўчирилган. Шундай қилиб, рўйхатда фақат 25 
сонига тенг ёки ундан кичик бўлган тартиблаштирилган оддий сонлар қолди. 
Умумий савол туғилади: р сонининг қандай унча катта бўлмаган қийматида ҳали рўхатда унга 
каррали бўлган сонлар қолади? Унга жавоб беришдан олдин, фаҳмлаймизки, агр р сони олдинги 
ўтишда рўйхатдан ўчирилиши керак бўлган сонга каррали ҳисобланса, у ҳолда кўриб чиқишни р·р 
сонидан бошлаш керак бўлади, чунки 2р,…,{р—1)р - унга каррали бўлган сонлардан кичиклари 
одинги ўтишларда рўйхатдан ўчирилган. Бу кузатиш ўша битта сонни бир мартадан ортиқ 
ўчирилишини олдини олишга имкон беради. Равшанки, р·р кўпайтма n сонига қараганда катта 
бўлиши керак, шунинг учун р сони пастки томонга бутун сонгача яхлитланган 
√𝑛 қийматдан ошиб 

---

кетолмайди. Математик тилада бу {
√𝑛} сифатида, яъни “пол” (пастга яхлитлаш, floor) функцияси 
дейиладиган функция ёрдамида ёзилади. Қуйида келтирилган алгоритм псевдокодида ҳисоблаш 
учун {
√𝑛} тайёр функция ишлатилиши кўзда тутилади. Муқобил вариант сифатида циклни 
ҳисоблашни давом эттирилиши сифатида р · р ≤ n тенгсизликнинг қийматини текшириш мумкин. 
Sieve (n) алгоритми (Эратосфен решетоси) 
// Эратосфен решетосининг ишлатилиши 
// Кириш маълумотлари: n≥2 мусбат бутун сон 
// Чиқиш маълумотлари: n сонига тенг ёки ундан кичик бўлган L
оддий сонлар массиви 
for р←2 to n do 
А[p]←р 
for р←2 to {√n do // псевдокоддан олдинги абзацга қаранг 
if А[p]≠0 // р га каррали элементлар ҳали олдинги
j←р·р // ўтишларда ўчирилмаган 
while j≤n 
А[j]←0 // ўчирилган сифатда бу элементни ва
j←j+р // кейинги р га каррали элементларни
белгилаймиз 
Демак, энди Эратосфен решети алгоритмини сиз ўрта мактабда ўтган усул билан 
бирлаштириш мумкин, бу билан иккита мусбат сонларга ЭКУБни қидириш мутлақо қонуний 
алгоритмини оласиз. Эътибор беринг, бу алгоритмда бир ёки ҳар иккала кириш параметрлари 1га 
тенг бўладиган хусусий ҳолни кўзда тутиш керак. Мадомики, математиклар 1 сонини оддий 
ҳисоблашмасада, қатъий айтганда, бу усул бундай ҳолда ҳам ишлаши керак эмас.
Бу бўлимни якунлашдан олдин, яна бир муҳим мулоҳазани қилиш зарур. Бу бўлимда кўриб 
чиқилган мисоллар бу алгоритмларнинг кўпчилиги кенг ишлатилишига, айримлари ҳатто 
компьютер дастурлари кўринишида ишлатилишига қарамасдан математик вазифаларга кирмайди. 
Масалаларни алгоритмларга ёйилишини билиш ҳам ишда, ҳам уйда вужудга келадиган кундалик 
эскирган муаммоларни ечишда ярайди. Замонавий дунёда алгоритмларнинг муҳимлигини англаш 
билан сизга бу ажойиб ахборот асри двигатели ҳақида янада кўпроқ билишни исташингиз мумкин.