To make the code even more efficient, we target the sections where most of the operations take place. In this case we look at the function which checks if the number is a prime or not.
In the present logic, we find all the divisors till N by iterating I over all 1 to n and checking if N is divisible by I. If I is divisible, COUNT is incremented by 1. Then COUNT is checked if it is = 2, and if so, it is a prime. I intend to make this process more efficient by providing two different methods, one by reducing the number of checks required, and the other by not requiring to count the divisors at all.
Method 1-
We assume the following: for any natural number x which is a divisor of N, there exists another y such that xy=N.
What this means is that for any divisor of N, there exists another divisor, whose product with the former is equal to N, i.e. divisors come in pairs.
Hence, when we find one of the divisors, the other one can be conveniently found by simply dividing N by that divisor. Further, this also means that we need to run that loop only till sqrt(N). (Think why this is so)
But what about numbers which are NOT perfect square? We can not run the loop for a non integer number of times can we? So we find the greatest integer smaller than the root of the number by using a function called floor(). Each time we encounter a divisor, we simply increment COUNT by 2 instead of 1.
However, if N is a proper square, then the number of divisors given by the function will be greater than the actual by 1 (Why?). So we simply check if the number is a perfect square(How? Hint: use floor()) and reduce the number of divisors by 1. Then we check if COUNT==2 and return True or False accordingly.
Method 2-
We assume the following: A number with even one divisor (not equal to 1 or itself) will NOT be a prime. The proof of assumption is self-evident by definition of prime.
Since we know that if we find EVEN ONE divisor in 2 to sqrt(N), the number is not prime, we can skip checking for other divisors the moment we find a divisor. This can be implemented by using the fact that the return statement IMMEDIATELY stops the function. If we iterate through the complete loop and still don't find a divisor, we can simply return that it is True.
ANALYSIS-
Now that we have three different ways (essentially only 2), let us analyse these to see which is the fastest.
Comparing the method given by Sourav and Method 1, we see that Method 1 has root n iterations whereas the former has n iterations. Hence, Method 1 is faster.
Comparing Method 1 and Method 2, we see that in the scenario that N is a prime number, both have equal number of iterations (sqrt N). But in the case of a Composite number, Method 2 runs only till it finds the first divisor and stops there, whereas Method 1 continues to loop. Further in Method 1, we required a COUNT variable which was not required in Method 2, making Method 2 more space efficient too. I have NOT provided the implementation of the above Methods to give you an opportunity to do so yourself.
Further Reading-
SPACE-TIME TRADE-OFF
ANALYISIS OF ALGORITHMS
BIG OH NOTATION