1.相减法
两个数,相等时,最大公约数为他们其中任意一个。不相等时,用大数减小数。得到的差和之前的那个小数再次相减,直到两个数相等,这两个中,任意一个都是最大公约数。(代码如下)
#include<stdio.h> int main() { int a = 0; int b = 0; printf('请任意输入两个数:'); scanf('%d%d', &a, &b); while((a-b) != 0) { if(a>b) a = a-b; else b = b-a; } printf('最大公约数为:%d\n', b); return 0; }
2.穷举法
如果大数可以整除小数,那么最大公约数为小数。如果不能整除小数,那么这两个数就按大到小依次对比小数小的数求余,遇到都能够整除的,就是最大公约数。(代码如下)
#include<stdio.h> int main() { int a = 0; int b = 0; printf('请任意输入两个数:'); scanf('%d%d', &a, &b); if(a>=b) { int i =0; for(i=b; i>=1; i--) { if((a%i)==0 && (b%i)==0) { printf('最大公约数为:%d\n', i); break; } } } else { int j = 0; for(j=a; j>0; j--) { if((a%j)==0 && (b%j)==0) { printf('最大公约数为:%d\n', j); break; } } } return 0; }
3.辗转相除法
用大数对小数求余,若余数为0,则除数为最大公约数。若余数不为0,将此余数作为除数,小数作为被除数,重新求余,直到余数为0为止。此时的最大公约数为余数。例如:27和6. 27%6=3. 6%3=0. 所以最大公约数为3.(代码如下)
#include<stdio.h> int main() { int a = 0; int b = 0; printf('请输入两个数:'); scanf('%d%d', &a, &b); if(a >= b) { int c = a%b; while(c != 0) { a = b; b = c; c = a%b; } printf('最大公约数为:%d\n', b); } else { int d = b%a; while(d != 0) { b = a; a = d; d = b%a; } printf('最大公约数为:%d\n', a); } return 0; }
联系客服