A Solution: Prime Number Test

n = int(input("Enter a number: "))

number_is_prime = True
for i in range(2,n):
    if ((n % i)==0):
        number_is_prime = False

if (number_is_prime==True):
    print("The number {0} is prime".format(n))
else:
    print("The number {0} is not prime".format(n))

This is the most inefficient, brute-force way of doing it. Think about how you might modify the code to make it more efficient.

I can think of two easy ways of speeding this up straight away:

1. In the for loop, once one of the tests fails and the number_is_prime variable is set to False, do you need to keep testing the remaining values? No. You have your answer, and you can stop.
2. Do you need to test all values between 2 and n-1? You don’t. Think about what the largest number you need to test is.