Prime number program 

  Machine Learning in Python

Summary : In this program, we will learn another construct for loops, modulo division, use of flag variables, and for-else syntax.

 Program Logic

A prime number is an indivisible number. You cannot divide it with any number except itself. The logic to find if a number is prime or not, is to start dividing it by all the numbers starting with 2 and if it is not divisible by any of those numbers, then we can declare it as a prime number.

Here is the Program

print ( “Prime number program “)
user_input = input ( ” Enter a number greater than 1 – “)
user_input = int(user_input)

for i in range ( 2, user_input):
    if user_input % i == 0:
        print ( user_input, ” is not a prime number”)
        print ( “it is divisible by”, i)
        break
else:
    print ( user_input, “is a prime number”)

The initial 3 lines of the code should be pretty familiar to you already.   for loop

Similar to a while loop, for loop can also loop until a certain condition is met. The syntax looks like this.

for x in values :     
    # do something 

values can be a range of values which can be specified in a couple of ways. For example, you can say

for x in ["India", "United States", "China"] :     
    print (x) 

or, you can use a built-in python function called range() that returns a list of values. For example, the following code prints all the values from 1 to 10

for x in range(11):
     print (x ) 

In this case, the for loop runs from 2 all the way to the number that the user has input. Technically, we can just go until half of what the user enters, but we will correct it later.

for i in range ( 2, user_input):
     if user_input % i == 0:
         print ( user_input, " is not a prime number")
         ... 

Modulo Division

Once we are in the loop, we need to check if the number is divisible by i ( the index of the loop ). How do we check if a number is divisible or not ? If the remainder is 0, then the number is divisible – else it is not. Modulo division operator – % , gives us the remainder of a division operation. So, if the remainder of the division is 0, then it is not a primer number and we keep going to the next number until we go to the last number.

if user_input % i == 0:
     print ( user_input, " is not a prime number")
     print ( "it is divisible by", i)
     ... 

for – else syntax

What to do when we exit the loop ? That is when we know that the number is prime. Meaning, if all the divisions in the for loop have failed, we declare it as a prime number. In situations like this, we use the else syntax. This is peculiar to python as many standard languages do not have this kind of “else” syntax for loops.

for i in range ( 2, user_input):
     if user_input % i == 0:
         print ( user_input, " is not a prime number")
         print ( "it is divisible by", i)
         break
else:
     print ( user_input, "is a prime number") 

If the number is divisible by at least one number, then it is not a prime number – in which case, we want to break the for loop and not go into the else statement. It is precisely for that reason we use the break statement in the for loop.   Flag Variables

If we did not use the for-else syntax, how would we signal that the number is a prime number ? After running through the loop, and finding out that none of the numbers were able to divide the user’s input number, we now know that the user’s input number is a prime number. How would we know if we broke the loop intentionally (in which case it is not prime) or a break statement has broken the loop ( in which case it is prime ). This is where we use flag variables. These are not special variables – we just happen to store a “flag” like value in a variable.

This is not specific to python. In almost every programming language, variables can be used to store a value – some times these values can be used logically to be like a flag – red or green, black or white, True or False.

found_prime_flag = True 

In this case, we are using the variable found_prime_flag as a Boolean variable. If through the course of the program, we need to raise a flag indicating that the number is prime and keep it that way for future use in the program, we use variables as flags.

Let’s re-write the program without the for-else construct, but by using flag variables.

print ( “Prime number program “)
user_input = input ( ” Enter a number greater than 1 – “)
user_input = int(user_input)
for i in range ( 2, user_input):
	if user_input % i == 0:
	print ( user_input, ” is not a prime number”)
	print ( “it is divisible by”, i)
	break
else:
	print ( user_input, “is a prime number”)

print ( “Prime number program “)
user_input = input ( ” Enter a number greater than 1 – “)
user_input = int(user_input)
found_prime_flag = True
for i in range ( 2, user_input):
	if user_input % i == 0:
		print ( user_input, ” is not a prime number”)
		print ( “it is divisible by”, i)
		found_prime_flag = False
		break
	if found_prime_flag == True :
		print ( user_input, ” is a prime number”)

Right after the loop exits, we know if the loop was broken because a prime number has been found (in which case, we set the flag to False), or loop exited after exhausting all the values in range ( in which case, the flag would still be set to True).

According to the status of the flag, we can now know if the user’s input is a prime number or not.

There are many other situations where variables are used as flags. For example, if the user input is a prime number, print the square of the number – else print the number as-is.