Chapter 23 – Finding Prime Numbers 369

31. 
    

    create the sieve

    
    


32. for i in range(2, int(math.sqrt(sieveSize)) + 1):


33. pointer = i * 2


34. while pointer < sieveSize:


35. sieve[pointer] = False


36. pointer += i

The for loop on line 32 goes through each integer from 2 up to the square root of sieveSize.
The variable pointer will start at the first multiple of i after i (which will be i * 2). Then
the while loop will set the pointer index in the sieve list to False, and line 36 will
change pointer to point to the next multiple of i.

38. 
    

    compile the list of primes

    
    


39. primes = []


40. for i in range(sieveSize):


41. if sieve[i] == True:


42. primes.append(i)

After the for loop on line 32 completes, the sieve list will contain True for each index that is
a prime number. We can create a new list (which starts as an empty list in primes) and loop over
the entire sieve list, and appends and numbers if sieve[i] is True (meaning i is prime).

44. return primes

The list of prime numbers is returned on line 44.

Detecting Prime Numbers

The isPrime() function in primeSieve.py checks if the number can be divided evenly by a
range of numbers from 2 to the square root of the number. But what about a number like
1 , 070 , 595 , 206 , 942 , 983? If you pass this integer to isPrime(), it takes several seconds to
determine if it is prime or not. And if the number is hundreds of digits long (like the prime
numbers in next chapter’s RSA cipher program are), it would take over a trillion years to figure
out if that one number is prime or not.

The isPrime() function in primeSieve.py is too slow for the large numbers we will use in the
RSA cipher. Fortunately there is an algorithm called the Rabin-Miller Primality Test than can
calculate if such large numbers are prime or not. We will create a new isPrime() function in
rabinMiller.py that makes use of this better algorithm.