“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