[Tutor] Prime Numbers

[Steven D'Aprano]

On Mon, Dec 16, 2013 at 09:49:23AM +0100, Rafael Knuth wrote:

> That's actually a good example. Let me explain what I feel confused about.
> Print actually runs through the entire loop.

No it doesn't. Print has nothing to do with loops. It just happens that 
the body of the loop -- the thing that gets run each time -- may happen 
to contain print. But it's not the print that does the looping, it's the 
"for" command.

It's hard to see what happens inside a loop without using print, which 
is why examples so often include print. But the print is incidental -- 
we could take the print out, let the loop run, and although you can't 
see any output, it's still looping:

x = 0
for i in range(10000)
    x += 1

# now, at the end, after the loop is finished:
print(x)


If you run that, you'll see that x now has the value ten thousand, 
instead of zero, thus proving that the for loop ran ten thousand times, 
even though print only ran once.

Remember, for loops have two main parts:

the head of the loop, which looks something like these examples:

    for object in list_of_objects:

    for i in range(99):

    for char in "Hello World!":

    for item in [1, 2, 4, 8, 16]:

and so on. The general pattern is

    for NAME in EXPRESSION:

That's the head of the for-loop. The body is an indented block of code, 
and it can contain *anything*. One line or 1000 lines, it doesn't 
matter. It can contain other loops, if statements, you name it. Even 
print.

    print("about to start a for loop")
    for item in something:  # the head
        # the body
        print("inside the for loop")
        result = do_calculation()
        number = result + 99
        print("stuff happening in here...")
        # when we get to the end of the body, control jumps 
        # back to the head of the for-loop
    # Because the next line is NOT indented, it is not
    # part of the for-loop body, but will run only when 
    # the for-loop is done.
    print("for-loop is finished")


Once a for-loop begins, Python will run the body as many times as 
needed: once, twice, a million times, sometimes even zero times, until 
one of four things happen:

- the for-loop finishes normally, by running out of values;

- the body of the loop executes a "break" statement, which immediately
  jumps to the outside of the loop;

- the body of the loop executes a "return" statement (only inside 
  functions) which immediately exits the function; or

- an exception is raised, either deliberately with the "raise" command,
  or accidentally by an error.


But the important thing is that one of those things must be actually 
executed. It's not enough that it is inside the loop, if the code is 
never run. Compare the difference between these two loops:


for letter in "ABCD":
    if letter == "x":
        print("exiting the loop immediately!"
        break
    print(letter)



for letter in "ABCD":
    if letter == "C":
        print("exiting the loop immediately!"
        break
    print(letter)





>  But let's change the
> program like this:
> 
> def RangeOfNumbers (n):
>     for i in range(n):
>         return i
> 
> print(RangeOfNumbers(5))
> 
> When you run this program, your result is:
> 
> >>>
> 0

Correct. Because the return statement is executed, it jumps out of the 
loop and returns the current value of i, which is 0. The rest of the 
loop never runs.


> So, return only returns the first value within the loop.

Not so! Returns returns whatever value *at the time it is called*, 
which could be the first value, the second value, the third value..., or 
even a completely different value that has nothing to do with the loop 
variable:


def test():
    for i in range(100):
        print(i)
        if i == 100000000:
            return "That's a big number!"
        if i == 5:
            return "Five is not so big."



> If you want the loop run over the entire range of values, you have to
> change it like this:
> 
> def RangeOfNumbers (n):
>     List = []
>     for i in range(n):
>         List.append(i)
>     return List
> 
> print(RangeOfNumbers(5))
> 
> >>>
> [0, 1, 2, 3, 4]


Correct.


> Let's get back to my original program:
> 
> def is_prime(number):
>     for element in range(2, number):
>         if number % element == 0:
>             return False
>     return True
> 
> I was assuming that the for loop ends after the first round, just like
> in my first example above.

Nope, it ends when the condition "number % element == 0" is true, which 
then calls the line "return False". That may be true on the first round 
(is_prime(8), since 8%2 == 0) or the second round (is_prime(9), since 
9%2 == 1 but 9%3 == 0) or the one millionth round (if number is big 
enough).

If we knew that the condition would always exit on the first round, 
there would be no point in using a for-loop.


> But as you explained the for loop iterates through the entire range
> and only stops if a. there are no more values left to iterate through
> or b. the condition is met (return False if number % element == 0).

Correct!


> That's the tiny little detail I am confused about: What does return
> exactly do? Does it return only the first value within a loop or does
> it iterate through all values within a loop? (unless a given condition
> is met)

Neither. return returns whatever value you tell it to return. (Sorry for 
using "return" three times in one sentence.) It takes the value you give 
it, whatever that value may be, squirrels it aways somewhere, then exits 
the current function. When the current function exits, the code which 
called that function grabs the saved result, and either stores it in a 
variable, uses it elsewhere, or prints it, whatever the code wishes:


n = len("something")  

The len function *returns* 9, which then gets stored in variable "n".


print(len("carrot"))

Here, the len function returns 6, which is then immediately passed to 
print, which prints it.


values = [1, 2, 99, len("surprise"), 22, 88]

Here, the len function returns 8, which is then stored in the 4th 
position of the list, which is stored in variable "values".


len("cat")

Here, the len function returns 3, but there is nobody waiting for the 
result, no variable to store it in. So Python does one of two things:

- when running in a script, the return result (3, in this case) is just 
harmlessly deleted, no harm done;

- when running in the interactive interpreter, at the >>> prompt, the 
result is printed.

But remember, the responsibility of all that does not belong to 
"return". All it does is grab the value you give it, make it available 
as the function result, then exit the function.


You can imagine that the len function, if written in Python, looks 
something like this:

def len(sequence):
    count = 0
    for item in sequence:
        count += 1
    return count


(This is not actually how len is implemented, but it could have been.)


Hope this clarifies a few things.



-- 
Steven