Hacking Secret Ciphers with Python

Chapter 23 – Finding Prime Numbers 367

Table 23-1. A blank sieve of Eratosthenes, with each number marked as “prime”.

Prime

1

Prime

2

Prime

3

Prime

4

Prime

5

Prime

6

Prime

7

Prime

8

Prime

9

Prime

10

Prime

11

Prime

12

Prime

13

Prime

14

Prime

15

Prime

16

Prime

17

Prime

18

Prime

19

Prime

20

Prime

21

Prime

22

Prime

23

Prime

24

Prime

25

Prime

26

Prime

27

Prime

28

Prime

29

Prime

30

Prime

31

Prime

32

Prime

33

Prime

34

Prime

35

Prime

36

Prime

37

Prime

38

Prime

39

Prime

40

Prime

41

Prime

42

Prime

43

Prime

44

Prime

45

Prime

46

Prime

47

Prime

48

Prime

49

Prime

50

Mark 1 as “Not Prime” (since one is never prime). Then mark all the multiples of two (except for
two itself) as “Not Prime”. This means we will mark the integers 4 (2 × 2), 6 (2 × 3), 8 (2 × 4),
10, 12, and so on up to 50 (the largest number we have) are all marked as “Not Prime”:

Table 23-2. The sieve with one and the multiples of 2 (except 2 itself) marked as “not prime”.

Not

Prime

1

Prime

2

Prime

3

Not

Prime

4

Prime

5

Not

Prime

6

Prime

7

Not

Prime

8

Prime

9

Not

Prime

10

Prime

11

Not

Prime

12

Prime

13

Not

Prime

14

Prime

15

Not

Prime

16

Prime

17

Not

Prime

18

Prime

19

Not

Prime

20

Prime

21

Not

Prime

22

Prime

23

Not

Prime

24

Prime

25

Not

Prime

26

Prime

27

Not

Prime

28

Prime

29

Not

Prime

30

Prime

31

Not

Prime

32

Prime

33

Not

Prime

34

Prime

35

Not

Prime

36

Prime

37

Not

Prime

38

Prime

39

Not

Prime

40

Prime

41

Not

Prime

42

Prime

43

Not

Prime

44

Prime

45

Not

Prime

46

Prime

47

Not

Prime

48

Prime

49

Not

Prime

50

Then repeat this with all the multiples of three, except for three itself: 6, 9, 12, 15, 18, 21, and so
on are all marked “Not Prime”. Then do this for all of the multiples of four (except for four
itself), and all of the multiples of five (except for five itself), up until eight. We stop at 8 because