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.
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'''