N gacha bo'lgan tub sonlarni topish. Erotasfen g'alviri
“Mathematics is the queen of the sciences and number theory is the queen of mathematics.” — Carl Friedrich Gauss
II qism. Sonlar nazariyasi. 3-dars
Oldingi darsimizda sizlar bilan qanday qilib butun sonni tub yoki murakkabligini tekshirishning oddiy usullaridan bir nechtasini ko’rib chiqqan edik. Bu darsimizda endi berilgan N sonigacha bo’lgan barcha tub sonlarni aniqlashning eng samarali usullaridan biri bo’lgan Erotasfen g’alviri deb ataluvchi algoritmni o’rganib chiqamiz.
N gacha bo’lgan tub sonlarni eng oddiy (naive) usullaridan biri bu har bir sonni birma-bir oldingi darsdagi usul orqali tublikka tekshirib chiqish hisoblanadi. Lekin, bunda algoritm ishlashi ancha sekin bo’ladi: O(n*sqrt(n)) Bu masalani yechishning bundan ko’ra ancha samarali va oddiy usuli mavjud.
Bu usul Erotasfen g’alviri deb atalib, qadimgi grek olimi Erotasfen tomonidan o’ylab topilgan.
Algoritm ta’rifi
Erotasfen g’alviri algoritmi qadamlari:
1. 2 dan n gacha bo’lgan butun sonlar massivini yaratib olamiz (1 tub son emasligi aniq)
2. Boshlanishiga p ni 2 ga (eng kichik tub son) teng deb olamiz.
3. p ning ko’paytuvchilarini, ya’ni 2*p, 3*p, 4*p, … n gacha murakkab son sifatida belgilab chiqamiz. p ning o’zi belgilanmasligi kerak.
4. p dan katta va N dan kichik birinchi belgilanmagan sonni topamiz. Bu bizda keyingi tub son bo’ladi va 3-qadamni shu son uchun ham bajaramiz.
5. Algoritm tugagan paytda belgilanmay qolgan sonlar bizga N gacha bo’lgan tub sonlarni beradi.
Bu algoritmni qanday ishlashini visual ko’rish uchun quyidagi animatsiyaga e’tibor bering.
Algoritm murakkabligi: O(n*log(log(n)))
To’liq ma’lumot uchun: Wikipedia.org
Algoritm implementatsiyaga mustaqil harakat qilib ko’ring. Biz esa siz bilan uni keyingi darsimizning keyingi qismida ko’rib chiqamiz.
Maqolani foydali deb hisoblasangiz uni do’stlaringizga ham ulashing.
Manba: @AlgorithmUz telegram kanali
YouTube kanalimiz: Algorithms Uzbekistan
Mavzular ro'yhati