Find LCM of two numbers in C, C++, Java and Python | faceprep

Program to find LCM of two numbers is discussed here. Two numbers are obtained as input and the prime factors of both the numbers are found. The product of the union of prime factors of both the numbers gives the LCM of the two numbers.

Program to find LCM of two numbers

#include <stdio.h>

int main()
{
int a, b, lcm;
printf(“\nEnter two numbers: “);
scanf(“%d %d”, &a, &b);

lcm = (a > b) ? a : b;

while(1)
{
if( lcm % a == 0 && lcm % b == 0 )
{
printf(“\nLCM of %d and %d is %d\n”, a, b,lcm);
break;
}
++lcm;
}
return 0;
}

#include <iostream>
using namespace std;

int main()
{
int a, b, lcm;
cout << “\nEnter two numbers: “;
cin >> a >> b;

lcm = (a > b) ? a : b;

while(1)
{
if( lcm % a == 0 && lcm % b == 0 )
{
cout << “\nLCM of ” << a << ” and ” << b << ” is “<< lcm << endl;
break;
}
++lcm;
}
return 0;
}

import java.util.*;
public class Main
{
public static void main(String args[])
{
int a,b,lcm,flag = 1;
System.out.print(“\nEnter two numbers : “);
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
lcm = (a > b) ? a : b;

while(flag == 1)
{
if( lcm % a == 0 && lcm % b == 0 )
{
System.out.println(“LCM of ” + a + ” and ” + b + ” is ” + lcm);
flag = 0;
break;
}
++lcm;
}
}
}

print(“Enter two numbers “)
a = int(input())
b = int(input())
lcm = 0
if(a > b):
lcm = a
else:
lcm = b
while(1):
if( lcm % a == 0 and lcm % b == 0 ):
print(“LCM of”,a,”and”,b,”is”,lcm)
break
lcm = lcm + 1

Program to find LCM of two numbers by finding their GCD

// LCM of two numbers in C

#include <stdio.h>

int GCD(int a, int b)
{
if (a == 0 || b == 0)
return 0;

if (a == b)
return a;

if (a > b)
return GCD(a-b, b);
return GCD(a, b-a);
}

int LCM(int a, int b)
{
return (a*b)/GCD(a, b);
}

int main()
{
int a,b;
printf(“\nEnter two numbers : “);
scanf(“%d %d”,&a,&b);
printf(“\nLCM of %d and %d is %d \n”, a, b, LCM(a, b));
return 0;
}

// LCM of two numbers in C++

#include <iostream>
using namespace std;

int GCD(int a, int b)
{
if (a == 0 || b == 0)
return 0;

if (a == b)
return a;

if (a > b)
return GCD(a-b, b);
return GCD(a, b-a);
}

int LCM(int a, int b)
{
return (a*b)/GCD(a, b);
}

int main()
{
int a,b;
cout << “\nEnter two numbers : “;
cin >> a >> b;
cout << “\nLCM of ” << a << ” and ” << b << ” is ” << LCM(a,b);
return 0;
}

// LCM of two numbers in java

import java.util.*;
public class Main
{
static int GCD(int a, int b)
{
if (a == 0 || b == 0)
return 0;

if (a == b)
return a;

if (a > b)
return GCD(a-b, b);
return GCD(a, b-a);
}

static int LCM(int a, int b)
{
return (a*b)/GCD(a, b);
}

public static void main(String args[])
{
int a,b;
System.out.print(“\nEnter two numbers : “);
Scanner sc = new Scanner(System.in);
a = sc.nextInt();
b = sc.nextInt();
System.out.println(“LCM of ” + a + ” and ” + b + ” is ” + LCM(a,b));;
}
}

# LCM of two numbers in python

def GCD(a, b):
if (a == 0 or b == 0):
return 0

if (a == b):
return a;

if (a > b):
return GCD(a-b, b);
return GCD(a, b-a);

def LCM(a, b):
return int((a*b)/GCD(a, b));

print(“Enter two numbers “)
a = int(input())
b = int(input())
print(“LCM of”,a,”and”,b,”is”,LCM(a,b))

Time Complexity : O(1)

lcm of two numbers