Count of common multiples of two numbers in a range
The problem at hand is to determine the count of common multiples of two given numbers within a specified range. In this scenario, we have two numbers, 4 and 6, and we are tasked with finding the count of common multiples of these numbers in the range from 1 to 100. This involves multiple concepts from number theory, including the concepts of greatest common divisor (GCD) and least common multiple (LCM).
Problem Statement
The problem statement revolves around finding the count of numbers that are divisible by both 4 and 6 in the range from 1 to 100. In other words, we need to identify the numbers that are common multiples of 4 and 6 within this range.
Example
Consider a simpler example to understand the concept better. Let's take two numbers, 3 and 5, and a range from 1 to 20. The common multiples of 3 and 5 in this range are 15 and 30. There are two common multiples within the specified range.
Idea to Solve the Problem
To solve this problem, we can utilize the properties of LCM and GCD. The LCM of two numbers, denoted as LCM(a, b), is the smallest positive integer that is divisible by both a and b. We can find the LCM using the formula:
LCM(a, b) = (a * b) / GCD(a, b)
Using this LCM value, we can calculate the count of common multiples within the given range.
Pseudocode
Here's the pseudocode to solve the problem:
function gcd(a, b):
if a = 0:
return b
return gcd(b % a, a)
function findLCM(a, b):
return (a * b) / gcd(a, b)
Algorithm Explanation
- The
gcd(a, b)
function calculates the greatest common divisor of two numbers using the Euclidean algorithm recursively. - The
findLCM(a, b)
function calculates the least common multiple of two numbers using the formula(a * b) / gcd(a, b)
. - In the
main
function, we define the given numbers (num1
andnum2
), as well as the lower and upper limits of the range. - We calculate the LCM of
num1
andnum2
. - The
count
is calculated by dividing the difference between the count of multiples oflcm
up toupperLimit
and the count of multiples oflcm
up tolowerLimit - 1
. - The final count is printed.
Java program
public class CommonMultiples
{
// Recursive method to return gcd of a and b
public static int gcd(int a, int b)
{
if (a == 0) return b;
return gcd(b % a, a);
}
// Method to return LCM of two numbers
public static int findLCM(int a, int b)
{
return (a / gcd(a, b)) * b;
}
public static void main(String[] args)
{
int num1 = 4;
int num2 = 6;
int lowerLimit = 1;
int upperLimit = 100;
int lcm = findLCM(num1, num2);
int count = (upperLimit / lcm) - ((lowerLimit - 1) / lcm);
System.out.println("Count of common multiples of " +
num1 + " and " + num2 + " between " +
lowerLimit + " and " + upperLimit + " is " + count);
}
}
Output
Count of common multiples of 4 and 6 between 1 and 100 is 8
Resultant Output Explanation
In the given example, with num1 = 4
, num2 = 6
, lowerLimit = 1
, and
upperLimit = 100
, we calculate the LCM as follows:
LCM(4, 6) = (4 * 6) / gcd(4, 6) = (24) / 2 = 12
Now, we calculate the count of common multiples of 12 within the range from 1 to 100:
count = (100 / 12) - ((1 - 1) / 12) = 8
Therefore, the output statement "Count of common multiples of 4 and 6 between 1 and 100 is 8" is derived.
Time Complexity
The time complexity of the given code is primarily determined by the calculation of the GCD and LCM. The Euclidean algorithm for GCD calculation has a time complexity of O(log(min(a, b))), and finding the LCM using the GCD takes constant time. The overall time complexity of the code is therefore O(log(min(a, b))).
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment