Repetition in Python: Prime or Non-Prime

Here’s a game that can illustrate the use of a for loop, and some other ideas as well. The computer presents the player with large numbers, one at a time. The player has to guess whether each number is prime or non-prime. A prime number does not have any divisors except 1 and  itself. 3, 5, 11, and 17 are prime numbers. The game ends either when a specific number of guesses have been made, or when the player makes a specific number of mistakes.

A key problem to solve in this game is to determine when a number is prime. The computer must be able to determine whether the player is correct, and so for

any given number there must be a way to figure out whether it is prime. Other­wise, the program for this game is not complicated:

while game is not over:

select a random integer k

print k and ask the player if it is prime

read the player’s answer

if player’s answer is correct:

print “You are right”

else:

print “You are wrong.”

The mysterious portion of this program is the if statement that asks if the player’s answer is correct. This means that the program must determine whether the number K is prime and then see if the player agrees. How can it be determined that a number is prime? A prime number has no divisors, so if one can be found, then the number is not prime. The modulo operator % can be used to tell if a division has a remainder: if k % n = 0, then the number n divides evenly into k, and k is not prime.

To find out whether a number is prime, try dividing it by all numbers smaller than it and if any of them have a zero remainder, then the number is not prime. We need to use a for loop.

isprime = True

for n in range (1, K):

if k%n == 0:

isprime = False

After the loop has completed, the variable isprime indicates whether K is prime. This seems simple, if tedious. It does perform a lot of divisions. Too many, in fact, because it is not possible for any number larger than K/2 to divide evenly into K. A slightly better program is as follows:

Next, this section of program should be incorporated into a complete pro­gram that plays the game. If the game is supposed to allow 10 guesses, then the first step is to repeat the whole thing 10 times:

import random

correct = 0                # The number of correct guesses

for iteration in range(0, 10):       # 10 guesses

Now, select a number at random. It should be large enough so that it is hard to see immediately if it is prime, although even numbers are a giveaway:

K = random.randint(10000, 1000000)   # Generate a new number

Next, print a message to the user asking for their guess, and read it:

print (“Prime or Not: Is the number “,K,” prime? (yes or no)”)

answer = input()       # Read the user’s choice

The user types in a string, “yes” or “no,” as their response. The variable isprime was used in the program that determines whether K is prime is logical, being True or False. It could be made into a string, so that it is the same as what the user typed, and then it could be compared directly against the user’s input:

isprime = “yes”

Now comes the code for determining primality as coded above, except with isprime as a string:

At this point the variable isprime is either “yes” or “no,” depending on whether K is actually prime. The user’s guess is also “yes” or “no.” If they are equal, then the user guessed correctly.

if isprime==answer:

print (“You are correct!”)

correct = correct + 1

else:

print (“You are incorrect.”)

Finally, the outer loop ends, and the result is printed. The value of the vari­able correct is the number of correct guesses the user made, because it was incre­mented every time a correct answer was detected. The last statement is

print (“You gave “,correct,” right answers out of 10.”)

This program can be found on the CD in the directory “primegame.”

1.  Exiting from a Loop

A clever programmer would notice a serious inefficiency with the prime number program. When it has been determined that the number is not prime, the loop continues to divide more numbers into k until k/2 of them have been tried. If k= 999992, then it is known after the first iteration that the number if not prime; it is even, so can’t be prime. But the program continues to try nearly another half million numbers anyway. What is needed is a way to tell the program that the loop is over. There is a way to do this.

A loop can be exited using the break statement. It is simply the word break by itself. The correct way to use this in the program above is as follows:

for n in range (1, int(k/2))  # Divide K by all numbers < K/2

if k%n == 0:                  # If the remainder is 0 then n

isprime = “no”                # divides evenly into K: not

# prime

break

This loop terminates when the number k is known to be not prime. The state­ment following the loop is executed next. This can save a lot of computer cycles, but does not make the program more correct – just faster.

A variation on this is the continue statement. This statement results in the next iteration of the loop being started without executing any more statements in the current iteration. This avoids doing a lot of work in a loop after it is known it’s not necessary. For example, doing some task for a list of names, except for people named “Smith,” could use a continue statement:

for name in (‘Jones’,’Smith’,’Peters’,’Sinatra’,’Bohr’, ‘Conrad’):

print (name);

if name == ‘Smith’:

continue

# Now do a bunch of stuff …

Both the break and continue do the same thing in while and for loops.

Modifying the loop variable does not change the number of iterations the loop will execute. In fact, it has no effect. This loop demonstrates that:

for i in range(0, 10):

print (“Before “,i)

i = i + 1000

print (“After “,i)

It prints

Before 0

After 1000

Before 1

After 1001

and so on. It seems that the value of i changes after the assignment for the re­mainder of the loop and then is set to what it should be for the next iteration. This makes sense if Python is treating the range as a set of elements (it is), and it assigns the next one to i at the beginning of each iteration. Unlike a while loop, there is no test for continuation. In any case, changing i here does not alter the number of iterations and can’t be used in place of a break.

2.  Else

The idea that the loop can be exited explicitly makes the normal termination of the loop something that should be detectable, too. When a while or for loop ex­its normally by exhausting the iterations or having the expression become False, it is said to have fallen through. When the for loop in the prime number program detects a factor, it executes a break statement, thus exiting the loop. What if it never does that? In that case, no factor exists, and the number is prime. The pro­gram as it stands has a flag that indicates this, but it could be done with an else clause on the loop.

The else part of a while or for loop is executed only if the loop falls through; that is, when it is not exited through a break. This can be quite useful, especially when the loop is involved in a search, as will be discussed later. In the case of the prime number program, an else could be used when the number is prime, as follows:

An else in a while loop occurs when the condition becomes false. Consider a loop that reads from input until the user types “end” and is searching for the name “Smith:”

inp = input()

while (inp != “Smith”):

s = input()

if s == “end”:

break

else:

print (“Smith was found”)

# When the program reaches this point it is no

# longer known whether Smith was found.

Of course, the else is not required, and some programmers believe it is even harmful. There are always other ways to accomplish the same thing.

Source: Parker James R. (2021), Python: An Introduction to Programming, Mercury Learning and Information; Second edition.