首页 > 代码库 > 数论--欧几里得定理(求最大公约数)

数论--欧几里得定理(求最大公约数)

辗转相除法:

 1 #include<iostream> 2 using namespace std; 3 int gcd(int a,int b) 4 { 5     return a%b==0 ? b : gcd(b,a%b); 6 } 7 int main() 8 { 9     int a,b;10     cin>>a>>b;11     cout<<gcd(a,b);12     return 0;13 }

辗转相减法:

 1 #include<iostream> 2 using namespace std; 3 int gcd(int a,int b) 4 { 5     if(a>b) 6     { 7         return gcd(a-b,b); 8     } 9     if(a<b)10     {11         return gcd(a,b-a);12     }13     //if(a==b)14     return a;15 }16 int main() 17 {18     int a,b;19     cin>>a>>b;20     cout<<gcd(a,b);21     return 0;22 }

 

数论--欧几里得定理(求最大公约数)