C/C++ Program to Find the Largest Divisor of a Number

Write a program to find the largest divisor of a number in C/C++. The program should print the greatest proper divisor of input number – N. A number X is a proper divisor of a number Y if X divides Y and X is less than Y.

For example,

Input
2145
Output
715

Explaination
Proper Divisors of 2145 = { 1, 3, 5, 11, 13, 15, 33, 39, 55, 65, 143, 165, 195, 429, 715 }
Largest Divisor = 715

Approach

Let N be the input. The simplest way to solve this problem is to loop through all numbers in range [1, N-1] and print the largest number that divides N.

#include <stdio.h>
#include <math.h>

int largest_divisor(int n) {

	int i;
	for (i = n - 1; i >= 1; --i) {
		// if i divides n, then i is the largest divisor of n
		// return i
		if (n % i == 0)
			return i;
	}
	// we reach this point if n is equal to 1
	// there is no proper divisor of 1
	// simply return 0
	return 0;

}

int main() {

	int n;
	printf("Enter a Number: ");
	scanf("%d", &n);

	printf("Largest Divisor of %d = %d", n, largest_divisor(n));

}

Output

Enter a Number: 2145
Largest Divisor of 2145 = 715

Optimization

We can optimize the above program. The largest proper divisor of a number N can never be greater than N/2. If a number is greater than N/2, then it can never divide N. Thus, we only loop numbers in range [1, N/2].

#include <stdio.h>
#include <math.h>

int largest_divisor(int n) {

	int i;
	for (i = n / 2; i >= 1; --i) {
		// if i divides n, then i is the largest divisor of n
		// return i
		if (n % i == 0)
			return i;
	}
	// we reach this point if n is equal to 1
	// there is no proper divisor of 1
	// simply return 0
	return 0;

}

int main() {

	int n;
	printf("Enter a Number: ");
	scanf("%d", &n);

	printf("Largest Divisor of %d = %d", n, largest_divisor(n));

}

Output

Enter a Number: 2135
Largest Divisor of 2135 = 427

The problem you just solved was very simple. It won’t be enough to crack rounds of many companies. If you want to grab an offer from your dream company then you need to focus on enhancing your problem-solving skills. We recommend you to visit Coding Ninjas and check out their data structure, algorithm courses. You will learn about all the important algorithms and data structures from industry experts that will help you a lot in cracking coding interviews.

Read

Leave a Comment

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