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[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

Leave a Comment

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