[Tutor] Prime Numbers

[spir]

On 12/15/2013 05:54 PM, Rafael Knuth wrote:
> Hej,
>
> I stumbled upon this program here (Python 3.3.0) and I don't quite
> understand how the for loop plays with the return True statement:
>
> def is_prime(number):
>      for element in range(2, number):
>          if number % element == 0:
>              return False
>      return True

Notice that the statement "return True" is outside the for loop. We reach this 
statement if ever the loop runs completely, meaning we never "return False" from 
inside the loop, meaning the condition "number % element == 0" is never True. 
This means, in program semantics, that 'number' is a multiple of no other number 
in interval [2, number[, in other words that it is prime.

> Now, I would expect the following in case I call the function with the
> variable 3:
>
> number = 3
> for element in range(2, 3):
> 3 % 2 != 0:
> Loop ends and program returns True.

In the special case of number=3, there is only one number in interval [2, 
number[, thus the loop has 1 single pass, with element=2 (the name "element" is 
rather bad here). The condition is checked once only, for this value 2. You 
could graph the function's progess so:

number = 3
for n in [2, 3[:
     * (3 % 2 == 0) ? NO
After loop: function returns True.

> Let's do the same with the variable 9:
>
> number = 9
> for element in range(2, 9):
> 3 % 2 != 0:
> My assumption is that the program should end the loop after the first
> iteration again and it then should return True.

Let us re-write that using a graph like above (each line marked with '*' is a 
pass of the loop, with a new value of n/element):

number = 9
for n in [2, 9[:
     * (9 % 2 == 0) ? NO
     * (9 % 3 == 0) ? YES
           --> function returns False

For number=5, it would be:

number = 5
for n in [2, 5[:
     * (5 % 2 == 0) ? NO
     * (5 % 3 == 0) ? NO
     * (5 % 4 == 0) ? NO
After loop: function returns True.

For number=10, it would be:

number = 10
for n in [2, 10[:
     * (10 % 2 == 0) ? NO
     * (10 % 3 == 0) ? NO
     * (10 % 4 == 0) ? NO
     * (10 % 5 == 0) ? YES
          --> function returns False

> But instead, the program returns False (correctly for obvious reasons
> because 9 is not a prime number). Can anyone help me understand what
> error in reasoning I am making here?

Alles verstanden, jetzt?

Denis