Checking Whether a Number Is Prime

This lesson covers an algorithm for checking whether a number is prime, so you can understand an efficient way to test it. It's written for anyone who searched "Python prime number check" and landed here.

Whether a number is prime (only divisible by 1 and itself) can be determined by checking whether it's divisible by any number from 2 up to "its square root." If none of them divide it evenly, it's prime. The key insight is that stopping at the square root, rather than checking every single number, dramatically reduces the amount of computation needed.

The sample code uses the range range(2, int(n ** 0.5) + 1), effectively looping only "up to the square root." n ** 0.5 is one way to compute a square root in Python — math.sqrt() is another option. Compare the results for 17 and 18.

A common beginner mistake is not understanding the reasoning behind why checking only up to the square root is sufficient. This relies on the fact that in any pair of numbers that divide a given number evenly, one is always less than or equal to the square root and the other is always greater than or equal to it — so checking the smaller range is enough.

This is an important mathematical property that also underlies cryptographic techniques, and coming up with an efficient checking algorithm is one of the fundamentals of computer science. There's also a more advanced technique for finding many primes at once, called the Sieve of Eratosthenes.