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

1. The gcd(a, b) function calculates the greatest common divisor of two numbers using the Euclidean algorithm recursively.
2. The findLCM(a, b) function calculates the least common multiple of two numbers using the formula (a * b) / gcd(a, b).
3. In the main function, we define the given numbers (num1 and num2), as well as the lower and upper limits of the range.
4. We calculate the LCM of num1 and num2.
5. The count is calculated by dividing the difference between the count of multiples of lcm up to upperLimit and the count of multiples of lcm up to lowerLimit - 1.
6. 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))).