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 integer **n** and we are asked to find its smallest divisor except
1. The first approach that anyone would take is to start from **2** and then go on dividing
it with the number **n** and select the first number that divides **n. **
n = 130
n = 130
for i in range(2,n-1):
if 130 % i == 0:
print i
break

All this looks very cool and straight.Now say suppose **n is a prime number**.

May be **n** is 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 number **n=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**

linked **with the largest divisor 50**.

Similarly the **second smallest divisor** **4 is linked with second**

largest divisor 25. This goes on with 5 linked with 20 and **finally**

10 linked with 10. So if we want to generalize this, we can observe

that if any number **n** has 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->10

For our example that cross over point is** 10**. Also at the cross over

point **smaller 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 **n ** we 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 number **n** is an even number or an

odd number. If **n** is 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 of **n**.

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

given number **n** is 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'''