Skip to main content

gcd

rust_algorithms::numbers

Function gcd 

Source 
pub fn gcd(a: u64, b: u64) -> u64
Expand description

Eng katta umumiy bo’luvchi (EKUB / GCD) — Evklid algoritmi.

G’oya: gcd(a, b) = gcd(b, a mod b). Chunki a va b ning har qanday umumiy bo’luvchisi a - k·b ni ham bo’ladi. b nolga aylanganda a — javob.

  • Time: O(log min(a, b)), Space: O(1).

§Misol

use rust_algorithms::numbers::gcd;

assert_eq!(gcd(48, 18), 6);
assert_eq!(gcd(17, 5), 1);   // o'zaro tub
assert_eq!(gcd(0, 9), 9);