[Tutor] python Task
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"
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
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.
More information about the Tutor