赞
踩
如果大数可以整除小数,那么最大公约数为小数。如果不能整除小数,那么这两个数就按大到小依次对比小数小的数求余,遇到都能够整除的,就是最大公约数。
- int gcd(int a, int b)
- {
- int i;
- int min = a < b ? a : b;
- for (i = min; i >= 1; i--)
- {
- if (a % i == 0 && b % i == 0)
- break;
- }
- return i;
- }
用a对b求余,若余数为0,则除数b为最大公约数。若余数不为0,将此余数r作为新的除数,b作为新的被除数,重新求余,直到余数为0为止。此时的最大公约数为除数。
- int gcd(int a, int b)
- {
- int t;
- while(a % b)//当a%b为0时,跳出循环,最大公约数为b
- {
- r = a % b;
- a = b;
- b = t;
- }
- return b;
- }
- int gcd(int a, int b)
- {
- int r = a % b;
- if (0 == r)
- return b;//当余数为0时,b就为最大公约数
- else
- return gcd(b, r);
- }
当两个数相等时,最大公约数为他们其中任意一个;当两个数不相等时,用大数减小数得到的差和之前的那个小数再次相减,直到两个数相等,相等的两个中,任意一个都是最大公约数。
- int gcd(int a, int b)
- {
- if (a > b) a = a - b;
- if (a < b) b = b - a;
- if (a == b) return a;
- }
- int gcd(int a, int b)
- {
- if (a == b) return a;//当a=b时,返回
- if (a < b)
- {
- return gcd(a, b - a);
- }
- return gcd(a - b, b);
- }
- int gcd(int a, int b)
- {
- int result = 1, i;
- for (i = 2; i <= a && i <= b; i++)
- {
- while (a % i == 0 && b % i == 0)
- {
- result *= i;
- a /= i;
- b /= i;
- }
- }
- return result;
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。