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 = 715Optimization
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 = 427The 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