最大公因数：欧几里得算法

 简述

        求两个数字 m和n 的最大公因数，假设r是m%n的余数，只要n不等于0，就一直执行

m=n，n=r

举例

以18和12为例

m      n        r
18  %  12   =   6
12  %  6    =   0
6      0
所以最大公因数为：6

代码实现

#include<iostream>
using namespace std;//greatest common divisor
unsigned long long gcd(unsigned long long m,unsigned long long n)
{while(n!=0){unsigned long long r=m%n;m=n;n=r;}return m;
}int main(void)
{int result=gcd(18,12);cout<<"18和12的最大公因数为:"<<result<<endl;return 0;
}