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

Read

Leave a Comment

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