欧几里得算法+递归
#include <iostream>
using namespace std;
int gcd( int x, int y)
{
if ( x % y == 0) return y;
else return gcd( y , x % y);
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a , b) << endl;
return 0;
}
笨蛋算法+递归
#include <iostream>
using namespace std;
int gcd( int a , int b)
{
int ans;
if ( a > b ) swap( a , b);
for (int i = 1 ; i <= a ; i ++ ){
if ( a % i == 0 && b % i == 0 ) ans = i ;
}
return ans;
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a , b) << endl;
return 0;
}
犯规做法,使用algorithm自带的__gcd函数(注意:两个下划线)
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a ,b ;
cin >> a >> b;
cout << __gcd(a,b) << endl;
return 0;
}
不犯规做法
#include <iostream>
using namespace std;
int gcd( int a , int b)
{
int ans;
if ( a > b ) swap( a , b);
for (int i = 1 ; i <= a ; i ++ ){
if ( a % i == 0 && b % i == 0 ) ans = i ;
}
return ans;
}
int main()
{
int a, b;
cin >> a >> b;
cout << gcd(a , b) << endl;
return 0;
}