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.
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.
1. Establish the integer n
2. If n is even then 2 is the smallest divisor.
- Compute r = √n;
- Initialize divisor d = 3;
- While not an exact divisor and r ≠ √n
- 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