# C Program to Find Smallest Divisor of an Integer

Write a program to find smallest divisor of an integer in C.

For example,

```Input
2135
Output
5

Input
49
Output
7

Explaination
Divisors of 305 = { 5, 7, 35, 61, 305, 427, 2135 }
Smallest Divisor = 5

Divisors of 49 = { 7, 7, 49 }
Smallest Divisor = 7```

Note: ‘1’ is the divisor of every number. We are calculating the smallest divisor other than ‘1’.

## Brute Force Approach

It is pretty obvious that the smallest divisor of a number is always a prime number. So, we basically need to find the smallest prime factor of the input number. The prime factor of a number – N is never greater than the square root of N. Thus, we can find the smallest prime factor of N by iterating numbers from 2 to square_root(N) and checking if the number divides N or not. The first number that divides N is the smallest divisor of N.

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

int smallest_divisor(int n) {

int i;
for (i = 2; i <= sqrt(n); ++i) {
if (n % i == 0) {
return i;
}
}
return n;

}

int main() {

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

printf("Smallest Divisor of %d = %d", n, smallest_divisor(n));

}
``````

Output

``````Enter a Number: 2035
Smallest Divisor of 2035 = 5``````

## Efficient Approach

In this approach, we create a sorted list of prime numbers using Sieve of Eratosthenes algorithm. After that, we iterate the list of prime numbers and check if the number is a divisor of N or not. We only iterating prime numbers that are less than or equal to the square root of N since no prime factor of N can be greater than the square root of N.

Note: This approach is the only efficient if we need to find the smallest divisor of many numbers. If you need to find the smallest divisor of a few numbers, then using brute force is better.

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

int prime;	// prime number hash map
// prime[i] = 1 means i is prime
// prime[i] = 0 means i is not prime

int primeList;	// array containing only prime numbers
int pl_len;				// length of primelist

void SieveOfEratosthenes(int n = 100000) {

int p, j;

// set all elements of prime[] to 1
for (j = 0; j < n; ++j)
prime[j] = 1;

prime = 0; // 1 is not prime
for (p = 2; p <= sqrt(n); ++p) {
for (j = p * p; j < n; j += p) {
prime[j] = 0;
}
}

// creating list of prime numbers
pl_len = 0;
for (p = 2; p < n; ++p) {
if (prime[p] == 1)
primeList[pl_len++] = p;
}

}

int smallest_divisor(int n) {

int i = 0;
// iterating prime numbers less than square root of N
while (primeList[i] <= sqrt(n)) {
if (n % primeList[i] == 0)
return primeList[i];
++i;
}
return n;

}

int main() {

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

SieveOfEratosthenes(); // to create list of prime numbers - primelist

printf("Smallest Divisor of %d = %d", n, smallest_divisor(n));

}
``````

Output

``````Enter a Number: 47231
Smallest Divisor of 47231 = 73``````

Note: The above program only works if the largest prime number in primeList is greater than the square root of the input number N.