[Tutor] python Task

[Steven D'Aprano]

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