This is a very basic problem and the lessons that we learn from this problem can be very useful in tackling more complex problems. Say suppose we have an integernand we are asked to find its smallest divisor except 1. The first approach that anyone would take is to start from2and then go on dividing it with the numbernand select the first number that dividesn.n = 130 n = 130 for i in range(2,n-1): if 130 % i == 0: print i breakAll this looks very cool and straight.Now say suppose

n is a prime number.

May benis a very large prime number (1013). So are we

going to count all the way upto 1012 starting from 2 and check whether 1013 gets divided

by any one of these numbers on the way? That sounds little stupid and requires a lot of work.

Now the main question is :

Do we have a better way?In order to investigate into this matter lets start with few observations.

Let us take a numbern=100.We have the following

divisors of 100: [2,4,5,10,20,25,50]Let us take the first divisor

2. We can easily observe that:

Similarly we can take other numbers and observe the following:

So from this we can observe that

the smallest divisor 2 is

linkedwith the largest divisor 50.

Similarly thesecond smallest divisor4 is linked with second. This goes on with 5 linked with 20 and

largest divisor 25finally. So if we want to generalize this, we can observe

10 linked with 10

that if any numbernhas a divisor then that divisor is always linked

with another divisor. The general pattern is that a smaller divisor is

linked with a larger one and vice versa.Another interesting thing that can be observed is that if we go on

increasing the value of smaller divisor and consider the next larger

divisor, at the same time if we go on decreasing the value of the

larger divisor and consider the next smaller divisor then we reach

a cross over point.

2->4->5->10

50->25->20->10For our example that cross over point is

10. Also at the cross over

pointsmaller divisor = larger divisor.So what is 10 in our case? 10 is the square root of 100.

So once we find the square root of any number

nwe don't

need to look beyond the value of the square root for the smallest divisor.

The other side of the square root will always have the larger divisors.

Also we need to check if the given numbernis an even number or an

odd number. Ifnis even then we know that 2 will be its smallest

divisor. If it is odd we just need to start with 3 and go on checking

the next odd number until we reach the value of the square root ofn.

So the more efficient program for finding the smallest divisor of any

given numbernis as follows:from math import sqrt from math import floor def smallestDivisor(n): if n % 2 == 0: print "The smallest divisor of %d is %d" %(n,2) else: squareRootOfn = floor(sqrt(n)) for i in (3,squareRootOfn,2): if n % i == 0: print "The smallest divisor of %d is %d" %(n,i) break else: if i == squareRootOfn: print "The smallest divisor of %d is %d" %(n,1) print "The given number %d is a prime number" % (n) smallestDivisor(1024) smallestDivisor(63) smallestDivisor(1013) '''The outputs are as follows: The smallest divisor of 1024 is 2 The smallest divisor of 63 is 3 The smallest divisor of 1013 is 1 The given number 1013 is a prime number'''