Sonni tublikka tekshirish. I qism

"Mathematics is the queen of the sciences and number theory is the queen of mathematics." - Carl Friedrich Gauss

II qism. Sonlar nazariyasi. 2-dars

O'tgan darsimizda sizlar bilan ikki sonning EKUBi va EKUKini topishni ko'rib o'tgandik. Bu darsda sonni tublikka tekshirishning bir nechta sodda usullarini ko'rib o'tamiz.

Ta'rif: Tub son deb birdan katta bo'lgan va faqat o'ziga va birga bo'linadigan songa aytiladi.

Tub sonlarga oid masalalar dasturlash olimpiadalarida ko'p uchraydi va real hayotdagi masalalarda ham tez tez bunday masalalarga duch kelinadi. Shulardan eng oddiylaridan biri berilgan sonni tublikka tekshirish.

1-usul:

Sonni tublikka tekshirishning eng oddiy usuli - bu uni 2 dan boshlab o'zigacha bo'lgan sonlarga bo'lib chiqib tekshirish hisoblanadi. Agar son ularning birortasiga qoldiqsiz bo'linadigan bo'lsa, demak bu son tub emas.

Algoritm murakkabligi: O(n)

2-usul:

Yuqoridagi algoritmni quyidagicha yaxshilash mumkin. Masalan, 100 sonining bo'luvchilari 2, 4, 5, 10, 20, 25, 50 ko'rinib turibdiki uning eng katta bo'luvchisi 50 = 100/2.

Barcha natural sonlar uchun uning eng katta bo'luvchisi n/2 ga teng yoki kichik. Demak, tekshirishni n gacha emas, n/2 gacha olib borsak yetarli. Bunda tezlik ikki barobarga oshadi.

Algoritm murakkabligi: O(n/2)

3-usul:

Lekin, bu usulni yanayam yaxshilash mumkin. Boshlang'ich matematika bilimlarimizdan shu ma'lumki, tublikka tekshirishni sonning ildizgacha olib borish yetarli. Dasturlashda ildiz (sqrt()) amali ko'p resurs talab qilganligi bois tekshirishda i o'ziga ko'paytirgan yaxshiroq usul hisoblanadi.

Endi algoritm murakkabligi: O(sqrt(n)).

4-usul:

Bu algoritmni ham yanada optimallashtirish imkoni bor. Bunda 2 va 3 dan boshqa barcha tub sonlar 6k±1 (k natural son) ko'rinishda ifoda etilishi mumkinligini e'tiborga olish kerak.

Isbot: Barcha 6k+0, 6k+2, 6k+4 ko'rinishidagi sonlar 2 ga bo'linadi. 6k+3 ko'rinishidagi sonlar esa 3 ga. Demak, son tub bo'lsa, uni albatta 6k±1 ko'rinishida ifodalash mumkin. Masalan, 17 = 6*3-1, 19 = 6*3+1, 37 = 6*6+1, 101 = 17*6 - 1. Lekin, barcha 6k±1 ko'rinishidagi sonlar ham tub bo'lavermaydi. Masalan: 25, 35,...

Yuqoridagi qoidani algoritmimizga tatbiq etadigan bo'lsak, algoritmimiz yanayam tezroq ishlaydi.

Lekin, yuqoridagi eng optimal yechim ham 10^9 gacha bo'lgan sonlar uchun tez ishlaydi. Son kattalashgani sari (10^18) talab etilgan vaqt ham keskin ortib ketadi va bu yechim ham yetarli bo'lmay qoladi. Bunday holatlarda sonni tublikka tekshirishda ehtimollikka asoslangan algoritmlardan (Milner-Rabin) foydalanish kerak bo'ladi. Bunday algoritmlarga keyingi darslarimizda to'xtalib o'tamiz.

Maqolani foydali deb hisoblasangiz uni do'stlaringizga ham ulashing.

Manba: @AlgorithmUz telegram kanali

YouTube kanalimiz: Algorithms Uzbekistan

"Eng yaxshi reklama - bu mamnun mijoz tomonidan qilingan reklama" - Philip Kotler