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

For example,

Input2135Output5Input49Output7ExplainationDivisors 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[100000]; // prime number hash map
// prime[i] = 1 means i is prime
// prime[i] = 0 means i is not prime
int primeList[10000]; // 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[1] = 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.

**Read**

- C Program to print prime numbers in the given range
- Write a program to count the number of prime numbers in a given range
- Print level order traversal of a binary tree