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

2021年4月18日19:10:09 发表评论 1,038 次浏览

本文概述

C ++
C
Java
Python3
C#
PHP

一个简单的解决方法是找出两个数的所有质因数，然后找出两个数中所有因数的并集。最后，返回联合元素的乘积。

一个有效的解决方法是根据以下公式计算两个数字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

//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#

//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.
?>

输出如下