Chapter 23 – Finding Prime Numbers 365

The only module primeSieve.py needs is the math module.

How to Calculate if a Number is Prime

primeSieve.py

7. def isPrime(num):


8. 
   

   Returns True if num is a prime number, otherwise False.

   
   


9. 
   


10. 
    

    Note: Generally, isPrime() is slower than primeSieve().

    
    


11. 
    


12. 
    

    all numbers less than 2 are not prime

    
    


13. if num < 2:


14. return False

We will program the isPrime() function to return False if the num parameter is a composite
number and True if the num parameter is a prime number. If num is less than 2 we know it is
not prime and can simply return False.

primeSieve.py

16. 
    

    see if num is divisible by any number up to the square root of num

    
    


17. for i in range(2, int(math.sqrt(num)) + 1):


18. if num % i == 0:


19. return False


20. return True

A prime number has no factors besides 1 and itself. So to find out if a given number is prime or
not, we just have to keep dividing it by integers and see if any of them evenly divide the number
with 0 remainder.

The math.sqrt() function will return a float value of the square root of the number it is
passed. The square root of a number can be multiplied by itself to get the number. For example,
the square root of 49 is 7, because 7 × 7 is 49.

For example, to find out if 49 is prime, divide it by the integers starting with 2:

49 ÷ 2 = 24 remainder 1

49 ÷ 3 = 16 remainder 1

49 ÷ 4 = 12 remainder 1

49 ÷ 5 = 9 remainder 4

49 ÷ 6 = 8 remainder 1