Qo’yilgan masala. Kesishmaydigan to’plam ostilari va birlashmalarini qidirish algoritmi. Ish tartibi

Dastur
Program L24; {Sodda algoritm. 1 - usul }
uses Crt;
var
n, d : integer;
begin
write('Butun sonni kiriting '); readln(n);
d := 1;
writeln(n, 'soning bo’luvchilari ');
repeat
if n mod d = 0 then write(d, ' ');
d := d + 1
until d > n div 2;
write(n)
end.
Lekin bu masalani yechishda ham mashinaga yordam bersa va uning ishini yengillashtirsa bo’ladi. Bu yerda yordamga yana matematika keladi. n soning bo’luvchilarini topish uchun sqrt(n) dan katta bo’lmagan bo’luvchilarni topish yetarli ekan. Qolgan barcha bo’luvchilar n ni topilgan bo’luvchilarga bo’lganda hosil bo’ladi.
Masalan, agar n=30 bo’lsa, u holda faqatgina 1, 2, 3, 5 (30 dan chiqadigan natural kvadrat ildizdan katta bo’lmagan son 5 ga teng) bo’luvchilarni topish yetarli, qolgan bo’luvchilarni esa 30 ni hosil bo’lgan sonlarga bo’lish orqali hosil qilsa bo’ladi:
30 div 1 = 30;
30 div 2 = 15;
30 div 3 = 10;
30 div 5 = 6.

Dasturni tuzishda muammo chiqib qoladi - butun sonlar to’plamida kvadrat ildizni chiqarish funksiyasi yo’q. Bu to’siqni yengib o’tish oson. Qanday qilib deysizmi? Buning uchun d ning 1 dan d*d gacha bo’lgan bo’luvchilarini tanlash siklini tashkil etish, agar kvadrat ildiz butun sondan iborat bo’lsa, bu holni asosiy sikl tugatilgandan so’ng alohida ko’rib chiqish kerak.
Nima uchun bunday qilish kerak?
Bu 36 soni uchun keltirilgan misolda ravshan bo’ladi. sqrt(36)= 6, dxd < 6 bo’lganicha-sikli;
d = 1, dxd = 1x1 = 1 < 36 (rost),
sikl davom etadi;
qoldiq topiladi: 36 mod 1 = 0; 1 va 36 ni 1 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 1 =36;
d = 2, dxd = 2x2 = 4 < 36 (rost),
sikl davom etadi;
36 mod 2 = 0;
2 va 36 ni 2 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 2 = 18;
d = 3, dxd = 3x3 = 9 < 36 (rost),
sikl davom etadi;
36 mod 3 = 0;
3 va 36 ni 3 ga bo’lgandagi butun son ekranga chiqariladi, 36 div 3 = 12;
d = 4, dxd = 4x4 = 16 < 36 (rost),
sikl davom etadi;
36 mod 4 =0;
4 va 36 div 4 = 9 ekranga chiqariladi;
d = 5, dxd = 5x5 = 25 < 36 (rost),
sikl davom etadi;
36 mod 5 <>0, ekranga hech narsa chiqarilmaydi,
sikl davom etadi;
d = 6, dxd = 6x6 = 36 < 36 (yolg’on), sikl tugatiladi.
d = 6 (dxd = n), 6x6 = 36 tekshiriladi (rost), 6 ekranga chiqariladi.
Agar sikl dxd <= n bo’lguncha davom etganda, u holda d = 6 da ekranga 6 va 36 div 6 = 6 chiqarilar edi, ya’ni ikkita olti, bu esa xato bo’lar edi