Steven D'Aprano steve at pearwood.info
Fri Oct 1 01:45:29 CEST 2010

```On Fri, 1 Oct 2010 08:38:31 am Dipo Elegbede wrote:

> 4.4 An integer greater than 1 is said to be prime if it is divisible
> by only 1 and itself. For example,
> 2, 3, 5 and 7 are prime numbers, but 4, 6, 8 and 9 are not.
> a) Write a function that determines whether a number is prime.

The first thing you need to know is that you can find out the remainder
after division by using the % operator. For example:

10 % 5 => 0  # 10 = 5*2
11 % 5 => 1  # 11 = 5*2 + 1
12 % 5 => 2  # 12 = 5*2 + 2

and so forth.

So you can check whether a number is divisible by another with:

if n % divisor == 0:
print "n is exactly divisible by divisor"
else:
print "n is not divisible by divisor"

So to find out whether a number n is prime, you need to check whether it
is divisible by each whole number starting from 2:

for divisor in range(2, n):
if n is divisible by divisor then n is not prime
# outside the loop
print "prime"

The above does a LOT of unnecessary work. Some improvements:

* Once you've discovered that a number is not prime, you can
exit the loop.
* There's no need to test every number up to n-1. Think about
what the greatest number you need to test would be.
* If a number isn't divisible by 2, then it can't possibly be
divisible by 4, 6, 8, 10, ... either. So apart from 2, there's
no need to check even numbers.

--
Steven D'Aprano
```