Email questions to the author: [email protected]

it is larger than 7.071, the square root of 50). We can do this because all the multiples of 9, 10,
11, and so on will already have been marked.

The completed sieve looks like this:

Table 23-3. A completed sieve of Eratosthenes. Not Prime 1

Prime 2

Prime 3

Not Prime 4

Prime 5

Not Prime 6

Prime 7

Not Prime 8

Not Prime 9

Not Prime 10

Prime 11

Not Prime 12

Prime 13

Not Prime 14

Not Prime 15

Not Prime 16

Prime 17

Not Prime 18

Prime 19

Not Prime 20 Not Prime 21

Not Prime 22

Prime 23

Not Prime 24

Not Prime 25

Not Prime 26

Not Prime 27

Not Prime 28

Prime 29

Not Prime 30

Prime 31

Not Prime 32

Not Prime 33

Not Prime 34

Not Prime 35

Not Prime 36

Prime 37

Not Prime 38

Not Prime 39

Not Prime 40

Prime 41

Not Prime 42

Prime 43

Not Prime 44

Not Prime 45

Not Prime 46

Prime 47

Not Prime 48

Not Prime 49

Not Prime 50

By using the sieve of Erastothenes, we’ve calculated that the prime numbers under 50 are 2, 3, 5,
7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. This sieve algorithm is good when we want to
quickly find out all the prime numbers in a certain range of numbers. It is much faster than using
the previous “divides test” algorithm to test if 2 is prime, then test if 3 is prime, then test if 4 is
prime, and so on.

The primeSieve() Function...............................................................................................................................

def primeSieve(sieveSize):

Returns a list of prime numbers calculated using

the Sieve of Eratosthenes algorithm.

sieve = [True] * sieveSize

sieve[0] = False # zero and one are not prime numbers

sieve[1] = False

The primeSieve() function returns a list of all prime numbers between 1 and sieveSize.
First, line 27 creates a list of Boolean True values that is the length of sieveSize. The 0 and
1 indexes are marked as False because 0 and 1 are not prime numbers.

Hacking Secret Ciphers with Python

The primeSieve() Function...............................................................................................................................

Returns a list of prime numbers calculated using

the Sieve of Eratosthenes algorithm.

Get our desktop app

Company

Features

Documentation

Resources