EKUBni topish (GCD)

Eng katta umumiy bo‘luvchini (EKUB, GCD) topish

EKUB (GCD, eng katta umumiy bo‘luvchi) — ikki sonni qoldiqsiz bo‘ladigan eng katta son.

int a = 36;
int b = 60;
int gcd = 1;

for (int i = 1; i <= a && i <= b; i++) {
  if (a % i == 0 && b % i == 0) {
    gcd = i;
  }
}

System.out.println("GCD: " + gcd);

Tushuntirish:

Bizga 36 va 60 sonlarining ikkalasini ham qoldiqsiz bo‘ladigan eng katta son kerak.

• Sikl 1 dan boshlanadi va kichikroq songacha (36) davom etadi.
• Har bir qadamda i ikkala sonning ham bo‘luvchisi ekanini tekshiramiz (qoldiq operatori % yordamida).
• Agar shunday bo‘lsa, gcd o‘zgaruvchisini shu qiymat bilan yangilaymiz.

Masalan:

• 36 % 12 == 0 va 60 % 12 == 0, demak, 12 ikkala sonning ham bo‘luvchisi.
• Keyinroq sikl eng katta umumiy bo‘luvchi sifatida gcd = 12 qiymatini topadi.

Shunday qilib, dastur GCD: 12 natijasini chiqaradi.