Solution Exercise 29

A prime number is an integer greater than 1 that is only divisible by one and itself. Write a function that determines whether or not its parameter is prime, returning True if it is, and False otherwise. Write a main program that reads an integer from the user and displays a message indicating whether or not it is prime. Ensure that the main program will not run if the file containing your solution is imported into another program.

Hint:
Consider using the modulus operator %

from math import sqrt
#Basic but ineffective solution
def is_prime1(n):
    if n <= 1:
        return False
    for x in range(2,n):
        if n % x == 0:
            return False
    return True

#A more effective solution
def is_prime2(n):
    if n <= 1:
        return False
    #Now we take care of the only even prime number
    if n == 2:
        return True
    #Now we know that all other even numbers can't be a prime
    if n % 2 == 0:
        return False
    #We will not need to check all numbers up to n.
    #We can stop at sqrt(n) +1
    #To avoid calling the sqrt function each time we store the result in a variable
    #At the same time we convert it to int
    sqrt_n = int(sqrt(n))
    #As we have taken care of the numbers below 3 we can start the range at 3
    for x in range(3, sqrt_n +1):
        if n % x == 0:
            return False
    return True
        
def main():
    for n in range(100):
        if is_prime2(n):
            print(n)
            
#This will ensure that the test code will not be executed if this module is imported    
if __name__ == '__main__':
    main()