当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:[NK]:求最小公倍数
题目描述
正整数A和正整数B?的最小公倍数是指?能被A和B整除的最小的正整数值,设计一个算法,求输入A和B的最小公倍数。
输入描述:
输入两个正整数A和B。
输出描述:
输出A和B的最小公倍数。
示例1
输入
5 7输出
35
解题思路:
1.传统解法:找出最小的那个数,然后都去逐渐除一个数。找出最大的那个。最后两数相乘除以这个数即可。
2.辗转相除法
示例代码:
#include<iostream> using namespace std; void Dispose(int Num1, int Num2) { if(Num1 == Num2) { cout<<Num1<<endl; return; } if(Num1 > Num2) { int temp = Num1; Num1 = Num2; Num2 = temp; } if(Num1 == 1 || Num1 == 0) { cout<<Num2<<endl; return; } int MaxData = 1; for(int i = 2; i <= Num1; i++) { if((Num1 % i == 0) && (Num2 % i == 0)) { MaxData = i; } } int data = Num1 * Num2 / MaxData; cout<<data<<endl; } void Dispose1(int Num1, int Num2) { int data; int Num1S = Num1; int Num2S = Num2; while(data = Num1 % Num2) { Num1 = Num2; Num2 = data; } data = Num1S * Num2S / Num2; cout<<data<<endl; } int main() { int Num1 = 0; int Num2 = 0; while(cin>>Num1>>Num2) { Dispose1(Num1, Num2); } return 0; }
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码
cs下一篇:没有了