flâneur

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

saved by

related reading