There are various questions one can ask while investigating primes algorithmically. One might be : Given a number *n*, is it prime ? A naive, brute force approach would be to iterate through all the numbers *i* from *0* to *n-1*, and test if *n%i ==0*. However, this approach would be naive in the extreme, and a more efficient approach can be devised by noting a few points.

- 0 and 1 are not primes
- 2 is a prime. However, all multiples of 2 are not prime. Hence we can reduce the numbers we have to inspect by 50%.
- If a number
*m*divides n, then*n/m*also divides*n*, and*n/m <=m*or vice-versa. Hence all we need is to examine numbers up to*sqrt(n)*and no further.

The Python code is shown below:

In [15]: import math def isPrime(n): if n <= 1 or n%2==0: return False if n==2: return True ulim = int(math.sqrt(n))+1 for i in range(3,ulim+1,2): if n%i ==0: return False return True In [16]: isPrime(6767) Out[16]: False In [17]: isPrime(62417) Out[17]: True

The code is available for download here : **primes.py**