|
欧几里得算法 欧几里得算法是用来求解两个不全为0的非负整数m和n的最大公约数的一个高效且简单的算法。该算法来自于欧几里得的《几何原本》。数学公式表达如下： 对两个不全为0的非负整数不断应用此式：gcd(m,n)=gcd(n,m mod n);直到m mod n为0时。m就是最大公约数证明：我们假设有a,b两个不全为0的数，令 a % b = r； 那么有 a = kb + r. 假设a,b的公约数是d。记做 d|a,d|b，表示d整除a和b。r = a - kb; 给这个式子两边同除以 d,有 r/d = a /d - kb / d，由于d是a ,b的公约数，那么r/d 必将能整除，即：b 和 a%b的公约数也是d。故：gcd(a,b) = gcd(b, a % b)。到此为止，已经证明了a和b的公约数和 b 和 a % b的公约数相等。直到a mod b为0的时候（因为即使 b > a,经过 a % b后，就变成计算gcd(b,a)。因此，a mod b的值会一直变小，最终会变成0），此时gcd(m,0) = m。因为0除以任何数都是0，所以m是gcd(m,0)的最大公约数。根据上面已经证明的等式gcd(a,b) = gcd(b, a % b)。可得：m就是最大公约数。定理得证。 下面是C++代码实现欧几里得算法。 #include
using namespace std;
int gcd(int m, int n);
int main()
{
int m, n;
cout > m >> n;
cout > n;
cout |