C语言例题4:最大公约数与最小公倍数 |
您所在的位置:网站首页 › 最大公约数和最小公倍数例题 › C语言例题4:最大公约数与最小公倍数 |
总结 C语言20题 问题描述【问题描述】输入两个大于1的整数,分别求出其最大公约数和最小公倍数并输出。 【输入形式】两个大于1的整数,空格分开 【输出形式】两个整数,用空格分开 【样例输入】4 6 【样例输出】2 12 思路辗转相除法 辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求两个正整数之最大公约数的算法。它是已知最古老的算法, 其可追溯至公元前300年前。 它的具体做法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。 例如:a=25,b=15,a%b=10,b%10=5,10%5=0,最后一个为被除数余数的除数就是5,5就是所求最大公约数。 代码 #include int gcd(int a,int b); int main(void){ int m,n,r; scanf("%d%d",&m,&n); r=gcd(m,n); printf("%d %d\n",r,m*n/r); return 0; } int gcd(int a,int b){ int t,r; if(a return b; }else{ return gcd(b,r); } } 实验结果 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |