算法设计（查找两个数字的LCM的程序）

本文概述

C ++
C
Java
Python3
C#
PHP

文章图片
两个数字的LCM(最小公倍数)是可以除以两个数字的最小数字。
【算法设计（查找两个数字的LCM的程序）】一个简单的解决方法是找出两个数的所有质因数，然后找出两个数中所有因数的并集。最后，返回联合元素的乘积。
一个有效的解决方法是根据以下公式计算两个数字a和b的LCM。

a x b = LCM(a, b) * GCD (a, b)LCM(a, b) = (a x b) /GCD(a, b)

讨论了求两个数的GCD的函数。使用GCD，我们可以找到LCM。
以下是上述想法的实现：
C ++

//C++ program to find LCM of two numbers #include < iostream> using namespace std; //Recursive function to return gcd of a and b long long gcd( long long int a, long long int b) { if (b == 0) return a; return gcd(b, a % b); } //Function to return LCM of two numbers long long lcm( int a, int b) { return (a /gcd(a, b)) * b; }//Driver program to test above function int main() { int a = 15, b = 20; cout < < "LCM of " < < a < < " and " < < b < < " is " < < lcm(a, b); return 0; }

//C program to find LCM of two numbers #include < stdio.h> //Recursive function to return gcd of a and b int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); } //Function to return LCM of two numbers int lcm( int a, int b) { return (a /gcd(a, b)) * b; } //Driver program to test above function int main() { int a = 15, b = 20; printf ( "LCM of %d and %d is %d " , a, b, lcm(a, b)); return 0; }

Java

//Java program to find LCM of two numbers. class Test { //Recursive method to return gcd of a and b static int gcd( int a, int b) { if (a == 0 ) return b; return gcd(b % a, a); }//method to return LCM of two numbers static int lcm( int a, int b) { return (a /gcd(a, b)) * b; }//Driver method public static void main(String[] args) { int a = 15 , b = 20 ; System.out.println( "LCM of " + a + " and " + b + " is " + lcm(a, b)); } }

Python3

# Python program to find LCM of two numbers # Recursive function to return gcd of a and b def gcd(a, b): if a = = 0 : return b return gcd(b % a, a) # Function to return LCM of two numbers def lcm(a, b): return (a /gcd(a, b)) * b # Driver program to test above function a = 15 b = 20 print ( 'LCM of' , a, 'and' , b, 'is' , lcm(a, b)) # This code is contributed by Danish Raza

//C# program to find LCM //of two numbers. using System; class GFG {//Recursive method to //return gcd of a and b static int gcd( int a, int b) { if (a == 0) return b; return gcd(b % a, a); }//method to return //LCM of two numbers static int lcm( int a, int b) { return (a /gcd(a, b)) * b; }//Driver method public static void Main() { int a = 15, b = 20; Console.WriteLine( "LCM of " + a + " and " + b + " is " + lcm(a, b)); } } //This code is contributed by anuj_67.

PHP

< ?php //PHP program to find LCM of two numbers //Recursive function to //return gcd of a and b function gcd( $a , $b ) { if ( $a == 0) return $b ; return gcd( $b % $a , $a ); } //Function to return LCM //of two numbers function lcm( $a , $b ) { return ( $a /gcd( $a , $b )) * $b ; } //Driver Code $a = 15; $b = 20; echo "LCM of " , $a , " and " , $b , " is " , lcm( $a , $b ); //This code is contributed by anuj_67. ?>

输出如下