Understanding Prime Numbers in Python, with Examples

Key Points

• Creating programs to interact with prime numbers is a common exercise for programmers learning a new language.
• A prime number is any number with only two factors: one and itself.
• There are three types of prime number exercises: checking if a number is prime, printing all prime numbers in a range, and calculating the sum of prime numbers in a range.
• Python offers multiple methods for approaching prime number exercises, including for loops, while loops, the sqrt() method, and flag variables.

To begin, creating programs that interact with prime numbers is a common exercise performed by programmers learning a new language. Creating a program to check if a number is indivisible is an excellent way to flex your muscles when learning a new coding language, especially if you continue to revise and optimize your program or recreate it using new methods as you learn them.

These coding exercises are an excellent way to utilize new methods and improve at a new programming language. Additionally, Python has several options for approaching a prime number exercise. So, let’s examine those.

What Is a Prime Number?

For starters, a prime number is any number with only two factors: one and itself. Thus, it is not indivisible if a number can be divided evenly by any number besides one. So, let’s examine some numbers and their factors and see whether they’re unfactorable or not.

To determine if a n is prime, you must take every number in the range between 2 and n-1 and divide it against n. If any one of those numbers divides evenly, then n is not unfactorable.

What Prime Number Exercises Can We Do in Python?

There are three types of prime number exercises. First, we can take an input and have the program tell us if the number we entered is indivisible. Secondly, we can put in a range of numbers and have the script print all the indivisible numbers in the range.

Finally, we can submit a range and have the code output the sum of all the unfactorable numbers in the range. Let’s look at the code we would write if we were doing these exercises.

Program to Check if a Number Is Prime

You can use a Python program to check if a number is prime in several ways. You can use a for loop, a while loop, the sqrt() method, or a flag variable. So, we’ll cover all these methods and explain how they work in detail, including example code you can utilize and learn from.

Basic For Loop

n = int(input("Enter a number: "))
if n > 1:
   for i in range(2,n):
       if (n % i) == 0: 
           print(n," is not a prime number") 
           break 
   else:
       print(n," is a prime number") 
else:
   print(n," is not a prime number") 

We’ll start by initializing a variable “n” and taking a user input for its value. Then, we want to check if n is greater than 1 since all prime numbers are. After that, we’ll initialize the variable “i,” which we will check against n to determine its unfactorable status.

We’ll determine a range for i’s value between 2 — the first prime number — and the value of n itself. Then, we’ll use the modulo operator (%), which returns the remainder of a division problem. If the remainder of a division problem is 0, then the two numbers are divisible.

Thus, we can use the modulo operator to determine if i is a factor of n. So, we’ll use an if statement that says if the method returns a remainder of 0, we print “n is not a prime number” and break the for loop, ending it.

We’ll include the else statement for the internal if. So, this one says that if the modulo operator never returns a 0, we print “n is a prime number.” Finally, we’ll use finish the first if, which checks if the number is greater than 1. If not, the program will print “n is not a prime number.”

This code works fine, but it’s suboptimal. If you check a particularly large number, it may take quite a while since the program must manually check the remainder of every number and n. So, we can further optimize this code to make the program run a bit faster. We’ll need to adjust the formula used to check whether n is prime to improve the code. So, let’s take a look at the new formula and code.

Optimized For Loop

n = int(input("Enter a number: "))
if n > 1: 
    for i in range(2, int(n/2)+1): 
        if (n % i) == 0: 
            print(n, " is not a prime number") 
            break 
    else:
        print(n, " is a prime number")
else:
    print(n, "is not a prime number")

Since a more optimal formula for checking prime numbers is to check against every number less than or equal to ((n/2)+1), we can adapt our program to check for that instead of every number less than or equal to n. Doing this can cut our program’s time of checking a number’s unfactorable status in half, giving us a more optimized code block.

While Loop

n = int(input('Please enter a number:'))
i = 2
flag = 0
while i<n: 
    if n%i == 0:
        flag = 1
        print (n,"is not a prime number");
    i = i + 1
if flag == 0: 
    print (n,"is a prime number"); 

In this case, we’ve replaced the for loop with a while loop. The for loop repeats code over a sequence of objects. Instead, the while loop will continue to execute code until its conditions are met.

So, we’ll start by initializing the variable “n” and taking the user input to determine its value. Then, we’ll create the “i,” which has a starting amount of 2 and a flag variable, which we set to 0.

After that, we’ll actually set up our while loop, which states that so long as the value of i is less than n, the code will continue to run. Then, we’ll use the modulo operator to check if i is a factor of n. If it is, then we adjust the flag variable to 1 and add 1 to i for the next iteration of the code.

If the flag variable is 0, then the number is prime. If it is not 0, then the number is factorable. You can further optimize this code block similarly to the for loop by altering the formula used to check if the number is prime.

Using sqrt()

from math import sqrt
n = int(input("Enter a number: "))
flag = 0 
if(n > 1):
	for i in range(2, int(sqrt(n)) + 1): 
		if (n % i == 0):
			flag = 1
		break 
	if (flag == 0):
		print(n," is a prime number")
	else:
		print(n," is not a prime number")
else:
	print(n," is not a prime number")

To start, we have to import the sqrt() function using the math module, which contains mathematical functions defined in the C standard. Then, we take a user input to determine what number to check.

Next, we’ll check if the number is greater than 1 since prime numbers must be greater than 1. Now, we’ll set the range of “i” from 2 to the square root of n plus 1. If any number in that range returns a 0 from the modulo operator, the number isn’t prime, and we break the for loop and set the flag variable to 1. Otherwise, the number is prime and we’ll print it.

You could run this script with while loops rather than for loops, though that wouldn’t affect the speed of the output. You could also run it without a flag variable. This formula is the most optimal one for checking if a number is indivisible. It checks the value of n against every number until the square root n is checked. Regarding worst cases, it’s actually the slowest when checking prime numbers because, in these cases, all numbers must be checked.

Code to Print All the Prime Numbers in a Range in Python

lower = int(input("Enter a the lower limit: "))
upper = int(input("Enter the upper limit: ")) 
print("The prime numbers between ", lower, " and ", upper, " are:")
for n in range(lower, upper + 1):
   if n > 1:
       for i in range(2, n):
           if (n % i) == 0:
               break
       else:
           print(n)

This program will calculate and print all prime numbers between the input range. We’ll start by taking user input for both the lower and upper limits. The print line is purely cosmetic, but it makes the program look nice and make more sense to use.

Then, we’ll initialize n in the for loop that says if “n” is within your upper and lower limits plus 1, we will continue the loop. We’ll initialize “i” with a range of 2 to n’s value. Next, we’ll use the modulo operator to check if i is a factor of n. If the remainder returns as 0, we break the for loop. Otherwise, we’re going to print the number.

This code is one of the ones that might take some time to run. When I input a range of 1 to 7000, it took several seconds before the script output anything. So, don’t be surprised if it takes a little bit for your computer to actually run the program. This specific block isn’t particularly well optimized.

Like the other programs in this cluster, it can be optimized by changing the formula to “for i in range (2, (num/2))” or “for i in range (2, int(sqrt(n)) +1)”. You could also change the for loops to while loops, though this would not necessarily impact the speed of the program.

Script to Print the Sum of All Prime Numbers in a Range in Python

lower = int(input("Please input a lower limit: "))
upper = int(input("Please input an upper limit: "))
print ("We will find the sum of prime numbers from", lower," to ",upper,".")
sum = 0
for n in range(lower, upper + 1):
    i = 2
    for i in range(2, n):
        if (int(n % i) == 0):
            i = n
            break;
    if i is not n:
        sum = sum + n
print("The sum of prime numbers from ", lower, " to ", upper, " is : ", sum)

To start this code, we’ll take user input for the upper and lower limits of the range in which we’ll be adding the prime numbers. Then, we start with a sum variable that has a value of 0.

We’ll establish a for loop with the variable “n,” which will have a range of values between the lower and upper limits plus 1. After that, we’ll initialize the variable “i” and set it to 2. We’ll put in another for loop that stipulates it running while i is in the range of 2 to n.

Now, we’ll use the modulo operator to determine if the input number is prime. If it is, we’ll add it to the sum variable. If not, we break the for loop. Finally, once we’ve finished the original for loop’s conditions, we’ll print the final value of the sum variable.

This code block will calculate all the prime numbers in the range you input and then add them all together. It’s worth noting that this script can take a while to run. Don’t be concerned if you input two numbers and it takes a little while to output a number.

You can optimize this code the same way as the other code blocks in the article: by changing the formula to find the numbers to “for i in range (2, (number/2))” or by importing the sqrt() function and using that. You could also change this code to use while loops rather than for loops, though doing so wouldn’t alter the optimization of the script.

The image featured at the top of this post is ©Mongta Studio/Shutterstock.com.