|
O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
NIZOMIY NOMIDAGI TOSHKENT DAVLAT PEDAGOGIKA UNIVERSITETI
Yunusova Yulduzning
“Boshlang’ich matematika kursi nazariyasi”
fanidan tayyorlagan.
TOSHKENT -2022.
Mavzu:Tub va murakkab sonlar.Eratosfen g’alviri.
Reja:
1.Psevdokod.
2.Segmentli elak.
3.Incremental elak.
4.Algoritmik murakkablik.
5.Eyler elakchasi.
Matematikada Eratosfen elaklari istalgan chegaragacha barcha tub sonlarni topish uchun qadimiy algoritmdir.
U buni birinchi tub sondan boshlab, har bir tub sonning karralilarini takroriy ravishda kompozitsion (yaʼni tub emas) deb belgilash orqali amalga oshiradi. ular orasida o'sha tubga teng. Bu elakning asosiy farqi boʻlib, har bir nomzod sonini har bir tub songa boʻlinish xususiyatini ketma-ket tekshirish uchun sinov boʻlinmasidan foydalanish hisoblanadi. Har bir topilgan tub sonning barcha koʻpaytmalari kompozit deb belgilangandan soʻng, qolgan belgilanmagan sonlar tub sonlar boʻladi.
Elak haqida eng qadimgi ma'lumot ( qadimgi yunoncha : kóskinon Eratosthenous , Eratosthénous ) Geraslik Nikomaxning Ar. 23 - asr boshlarida yozilgan muqaddimasida keltirilgan . Idoralar kitobi, uni ta'riflaydi va uni 3- asrdagi Kirenalik Eratosfenga bog'laydi . Miloddan avvalgi yunon matematigi .
Bir qator tub sonli eleklardan biri, bu barcha kichik tub sonlarni topishning eng samarali usullaridan biridir. U arifmetik progressiyalarda tub sonlarni topish uchun ishlatilishi mumkin .
Manba: BrainPoP.com
Tub son - bu aniq ikkita tabiiy son bo'luvchiga ega bo'lgan natural son : 1 raqami va o'zi.
Berilgan n dan kichik yoki unga teng barcha tub sonlarni Eratosfen usulida topish uchun:
2 dan n gacha bo'lgan ketma-ket butun sonlar ro'yxatini yarating : (2, 3, 4, ..., n ) .
Dastlab, eng kichik tub son p 2 ga teng bo'lsin.
2 p dan n gacha bo'lgan p ning o'sishi bilan sanash orqali p ning ko'paytmalarini sanang va ularni ro'yxatda belgilang (bular 2 p , 3 p , 4 p , ... bo'ladi ; p ning o'zi belgilanmasligi kerak).
Ro'yxatda belgilanmagan p dan katta bo'lgan eng kichik sonni toping . Agar bunday raqam bo'lmasa, to'xtating. Aks holda, endi p bu yangi sonni (keyingi tub son) tenglashtirsin va 3-bosqichdan boshlab takrorlang.
Algoritm tugagach, ro'yxatda belgilanmagan qolgan raqamlar n ostidagi barcha tub sonlardir .
Bu erda asosiy g'oya shundan iboratki, p ga berilgan har bir qiymat tub bo'ladi, chunki agar u kompozit bo'lsa, u boshqa kichikroq tubning ko'paytmasi sifatida belgilangan bo'lar edi. E'tibor bering, ba'zi raqamlar bir necha marta belgilanishi mumkin (masalan, 15 3 va 5 uchun ham belgilanadi).
Takomillashtirish sifatida 3-bosqichdagi raqamlarni p 2 dan boshlab belgilash kifoya , chunki bu nuqtada p ning barcha kichik karralari allaqachon belgilangan bo'ladi. Demak, p 2 n dan katta bo'lsa, 4-bosqichda algoritmni tugatishga ruxsat beriladi . Yana bir takomillashtirish shundan iboratki, dastlab faqat toq raqamlarni (3, 5, ..., n ) sanash va 3-bosqichda p 2 dan 2 p ga oshib, p ning faqat toq karralarini belgilashdir . Bu aslida asl algoritmda ko'rinadi. Buni g'ildirak faktorizatsiyasi bilan umumlashtirish mumkin , boshlang'ich ro'yxatni faqat koeffitsientlardan emas, balki birinchi bir necha tub sonlar bilan mos keladigan raqamlardan hosil qiladi ( ya'ni, raqamlar 2 ga mos keladi) va faqat shunday ko'paytmalar bo'lishi uchun mos ravishda sozlangan o'sishlarda hisoblash mumkin. Birinchi navbatda o'sha kichik tub sonlar bilan mos keladigan p lar hosil bo'ladi .
Misol
30 dan kichik yoki teng barcha tub sonlarni topish uchun quyidagi amallarni bajaring.
Birinchidan, 2 dan 30 gacha bo'lgan butun sonlar ro'yxatini yarating:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ro'yxatdagi birinchi raqam 2; roʻyxatdagi har 2-sonni 2 dan keyin 2 dan 2 ga koʻpaytirib sanab, kesib tashlang (bular roʻyxatdagi 2 ning barcha karralari boʻladi):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ro'yxatdagi 2 dan keyin keyingi raqam 3 ga teng; roʻyxatdagi har 3-raqamni 3 dan keyin 3 dan 3 ga oshirish orqali kesib tashlang (bular roʻyxatdagi 3 ning barcha karralari boʻladi):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ro'yxatda 3 dan keyin hali chizilmagan keyingi raqam 5; roʻyxatdagi har 5-raqamni 5 dan keyin 5 dan 5 ga koʻpaytirib sanash orqali kesib tashlang (yaʼni 5 ning barcha koʻpaytmalari):
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Ro'yxatda 5 dan keyin hali chizilmagan keyingi raqam 7; keyingi qadam ro'yxatdagi 7 dan keyin har 7-raqamni kesib tashlash bo'ladi, lekin ularning barchasi allaqachon chizilgan, chunki bu raqamlar (14, 21, 28) kichik tub sonlarning ko'paytmalari, chunki 7 × 7 kattaroqdir. 30 dan ortiq. Roʻyxatning ushbu nuqtasida chizilmagan raqamlar 30 dan past boʻlgan barcha tub sonlardir:
2 3 5 7 11 13 17 19 23 29
Do'stlaringiz bilan baham: |
