C/C++ Program to print multiples of 15 from m to n

Write a program to print multiples of 15 in a given range ( from m to n ) in C/C++.

Example,

Input
m: 10
n: 100
Output
15 30 45 60 75 90

Method 1: Brute Force

The simplest way to print multiples of 15 is to iterate each element from m to n and check if the number is divisible by 15 or not. If the number is divisible by 15, we print the number.

#include<stdio.h>

int main() {

	int n, m, i;
	printf("Enter m: ");
	scanf("%d", &m);
	printf("Enter n: ");
	scanf("%d", &n);
	for (i = m; i <= n; ++i) {
		if (i % 15 == 0)
			printf("%d ", i);
	}
	printf("\n");

}

Output

Enter m: 10
Enter n: 100
15 30 45 60 75 90

Time Complexity: O(n – m)

Method 2: Optimized

We can further optimize the program. You must have noticed that we are iterating all numbers from m to n. Instead of iterating all numbers in the given range, we find the first multiple of 15 that is greater than m. Let p be the first multiple of 15 greater than m. We can find the rest of the multiples of 15 by repeatedly adding 15 to p.

The code snippet given below calculates p ( first multiple of 15 >= m )

m = m - 1
p = m - m % 15 + 15

Example,

#include<stdio.h>

int main() {

	int n, m, i, p;

	// taking input
	printf("Enter m: ");
	scanf("%d", &m);
	printf("Enter n: ");
	scanf("%d", &n);

	// calculating p
	// p = first multiple of 15 >= m
	m = m - 1;
	p = m - m % 15 + 15;

	for (i = p; i <= n; i += 15) {
		printf("%d ", i);
	}
	printf("\n");

}

Output

Enter m: 30
Enter n: 120
30 45 60 75 90 105 120

Time Complexity: O((n – m)/15) = O(n – m)

Even though the time complexity of both methods is the same but Method 2 is about 15 times faster because the constant factor is very less compared to Method 1.

Read

Leave a Comment

Your email address will not be published. Required fields are marked *