# 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``````