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 : 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 : isPrime(6767) Out: False In : isPrime(62417) Out: True
The code is available for download here : primes.py