这是找出n个数字的GCD和LCM的代码。两个或更多不都是零的整数的GCD或最大公除数是将每个整数相除的最大正整数。GCD也被称为最大公因数。
两个数字的最小公倍数(LCM)是两个数字的倍数的最小数字（非零）。
算法
Begin Take two numbers as input Call the function gcd() two find out gcd of n numbers Call the function lcm() two find out lcm of n numbers gcd(number1, number2) Declare r, a, b Assign r=0 a = (number1 greater than number2)? number1: number2 b = (number1 less than number2)? number1: number2 r = b While (a mod b not equal to 0) Do r = a mod b a=b b=r Return r Done lcm(number1, number2) Declare a a=(number1 greater than number2)?number1:number2 While(true) do If (a mod number1 == 0 and a number2 == 0) Return a Increment a Done End
范例程式码
#include<iostream>
using namespace std;
int gcd(int m, int n) {
int r = 0, a, b;
a = (m > n) ? m : n;
b = (m < n) ? m : n;
r = b;
while (a % b != 0) {
r = a % b;
a = b;
b = r;
}
return r;
}
int lcm(int m, int n) {
int a;
a = (m > n) ? m: n;
while (true) {
if (a % m == 0 && a % n == 0)
return a;
++a;
}
}
int main(int argc, char **argv) {
cout << "Enter the two numbers: ";
int m, n;
cin >> m >> n;
cout << "The GCD of two numbers is: " << gcd(m, n) << endl;
cout << "The LCM of two numbers is: " << lcm(m, n) << endl;
return 0;
}
输出结果
Enter the two numbers: 7 6 The GCD of two numbers is: 1 The LCM of two numbers is: 42
