Algorithm to find smallest divisor of an integer.

To find the smallest divisor of an integer n is very straight forward. Just take the numbers 2, 3, 4, …,n and divide n with each of number in ascending order. But not an efficient method,  because it needs more iteration ( loops).

To efficiently calculate this problem we must reduce the loops by various techniques. And are follows.
All exact divisors of an integer are paired. What it means?. Nothing !.  for example an integer 24 have following divisors        2, 3, 4, 6, 8, 12. And each divisor has a pair.

Here 2 and 12 are paired. In another word  they are linked because
24/2   =   12 ;
2, 12 are smaller and bigger factors respectively.
Same way  3  and 8 are paired,    i.e.  (24/3    =    8;) and so on.
Smallest divisor

 

Here we can see that smallest divisor 2 is paired with largest divisor 12. 2nd smallest divisor is paired with 2nd largest divisor. And so on . if the integer is 36 we can see divisor 6 is paired with 6 itself.

In general case we have to consider only less than or equal to the biggest smaller divisor, now the problem!.how can we take that limit?.simple take √n,  all smaller divisors of an integer are less √n.

If n is an even number then its smallest divisor is 2. Now we need to consider only odd numbers. If we get n is the smallest divisor of n then it’s a prime,i.e. one is the smallest divisor.

 

Algorithm steps:

1. Establish the integer n
2. If n is even then 2 is the smallest divisor.
Else:

  1. Compute  r = √n;
  2. Initialize divisor d = 3;
  3. While not an exact divisor and r ≠ √n
  4. Generate next divisor d in odd sequence by  d = d +2;

If d is exact divisor and d ≠ n, then d is the smallest divisor of n
Else n is prime

Anwar Yakkiparamban

Anwar Yakkiparamban is the founder of Lauyou Learning. Prior to Lauyou learning, Anwar worked at ARD Engineering & Development, Qatar. He holds bachelor degree in Electronics and Communication Engineering from Govt. Engineering College Idukki.

You may also like...