✳flΓ’neur β€” a map of the web's best reading

Euclidean algorithm for computing the greatest common divisor - Algorithms for Competitive Programming

cp-algorithms.com Β· 1,123 words Β· saved by 1 readers

Given two non-negative integers β€Š β€Š π‘Ž <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> $a$β€Š and β€Š β€Š 𝑏 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> $b$β€Š, we have to find their GCD (greatest common divisor), i.e. the largest number which is a divisor of both β€Š β€Š π‘Ž <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi></math> $a$β€Š and β€Š β€Š 𝑏 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>b</mi></math> $b$β€Š. It's commonly denoted by β€Š β€Š gcd ( π‘Ž , 𝑏 ) <math xmlns="http://www.w3.org/1998/Math/MathML"><mo data-mjx-texclass="OP" movablelimits="true">gcd</mo><mo stretchy="false">(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo stretchy="false">)</mo></math> $\gcd(a, b)$β€Š. Mathematically it is defined as: (here the symbol "β€Š β€Š ∣ <math xmlns="http://www.w3.org/1998/Math/MathML"><mo>∣</mo></math> $\mid$β€Š" denotes divisibility, i.e. "β€Š β€Š π‘˜ ∣ π‘Ž <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>k</mi><mo>∣</mo><mi>a</mi></math> $k \mid a$β€Š" means "

Last update: October 15, 2024 &emsp; Translated From: e-maxx.ru Euclidean algorithm for computing the greatest common divisor &para; Given two non-negative integers $a$ and $b$ , we have to find their GCD (greatest common divisor), i.e. the largest number which is a divisor of both $a$ and $b$ . It's commonly denoted by $\gcd(a, b)$ . Mathematically it is defined as: $$\gcd(a, b) = \max \{k > 0 : (k \mid a) \text{ and } (k \mid b) \}$$ (here the symbol " $\mid$ " denotes divisibility, i.e. " $k \mid a$ " means " $k$ divides $a$ ") When one of the numbers is zero, while the other is non-zero, t

Explore this link on the map β†’

saved by

related reading