Prime Numbers โ€” The Lucky Ticket Problem

This lesson is one problem again. Your first program will be correct โ€” and once more it will not be good enough. But this time the trouble is different.

๐ŸŽฏ Section 1 โ€” The Problem

A school fair runs a lucky draw. Every ticket has a number, and a ticket wins when its number is prime: a number greater than 1 whose only divisors are 1 and itself. So 7 wins, and 12 does not, because 12 = 3 ร— 4.

Your job: for each ticket, write YES into out.txt if it wins, otherwise NO. Ticket numbers go up to 100.

This program is correct. Keep it โ€” you will use it again.

๐Ÿ“ˆ Section 2 โ€” Grow the Input

The fair grows. First the whole region joins, and ticket numbers go up to 10,000,000. Then comes the national draw, with 12-digit tickets, up to 1,000,000,000,000. Each draw still has only 5 tickets. Run the same program on each one.

  1. In your program, change "tickets-5.txt" to "tickets-region.txt". Save and run python check_ticket.py. It finishes โ€” but you have to wait.
  2. Now change the name to "tickets-country.txt" and run it again. Wait. It does not finish. Stop it with Ctrl+C.

Last lesson the trouble was too many questions. Here there are only 5 tickets, and the judge still gives your program 1 second. So the problem is not how many tickets there are: one ticket alone is already too slow.

๐Ÿงฎ Section 3 โ€” Count the Work

How slow is it, exactly? Start small and count by hand. Watch the program check two tickets, and count how many times it tries a divisor.

Count the checks
x = 12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Ticket 12. The program tries every divisor from 2 to 11 โ€” and it never stops early, even after it finds one.
1 / 108

Now make the program count its own work: add steps = 0 at the top, add 1 every time it tries a divisor, and print steps at the end.

python
steps = 0 tickets = [] with open("tickets-5.txt") as f: for line in f: tickets.append(int(line)) with open("out.txt", "w") as f: for x in tickets: found = False for d in range(2, x): steps = steps + 1 if x % d == 0: found = True if found: f.write("NO\n") else: f.write("YES\n") print(steps)

Run it on the small file. It prints 246: each ticket takes x - 2 checks, and 5 + 49 + 95 + 10 + 87 = 246.

Now run it on the region file, then work out the country file โ€” do not run that one:

๐Ÿงฉ Section 4 โ€” The Real Problem

The slow program tries every number below the ticket, so one ticket takes about as many checks as its own number. A bigger ticket means more checks, however few tickets there are.

Before any code, play with rectangles.

๐Ÿงฑ Section 5 โ€” The Rectangle Game

You have 36 square tiles. Press a number to lay them out with that many tiles in each row. If every row comes out full, you made a rectangle and it joins your list. Find every rectangle you can. Then change the tiles to 97 and do the same thing.

The rectangle game
Tiles:36
36 tiles ยท width = 36
Rows of 36 โ€” a full rectangle! Every row is full, with no tile left over.
Tiles per row
Rectangles found
36 ร— 1

What did you find for 97? A prime number of tiles makes no rectangle except one long row. And after you found all the rectangles for 36: which widths did you really need to try?

๐Ÿ’ก Section 6 โ€” Divisor Pairs

Look at your list for 36. Every rectangle has a twin turned on its side: 4 ร— 9 and 9 ร— 4. That is true of every number that is not prime: it is a small divisor times a big divisor. Divisors come in pairs.

Divisors come in pairs
36
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
The numbers from 1 to 36. Every number has the pair 1 ร— itself, so we leave that one out. Which other numbers divide 36?
1 / 10

The smallest a small divisor can be is 2. So the biggest a big divisor can be is half of x: 36 = 2 ร— 18, and 100 = 2 ร— 50. Nothing past half way can divide x, so we can stop half way instead of going all the way to x. Ticket 97 now takes 47 checks instead of 95.

๐Ÿ” Section 7 โ€” is_prime

Half way came from the biggest possible divisor. Now look at both sides of the pairs together.

The pairs meet in the middle
36 = 4 ร— 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
The pairs of 36. The small sides go up: 2, 3, 4. The big sides come down: 18, 12, 9.
1 / 6

So if no number up to the middle divides x, no bigger number can either: a bigger divisor would need a small partner, and we already tried all of those. Stop when d ร— d is bigger than x. In math this stopping point is called the square root of x.

How far do we have to look?

The idea, written as a function:

Watch it on two tickets: 97, which is prime, and 91, which is not. The buttons under the picture switch between them.

Stop at the middle
x = 97
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Ticket 97 again. This time we stop as soon as d ร— d is bigger than x.
1 / 18

That is the idea. Here is the same check written as code โ€” a function we call is_prime. Each press of Next runs one line, so you can watch d change. First ticket 97, which is prime; then press x = 91 for a ticket that is not.

is_prime, line by line
def is_prime(x):
d = 2
while d * d <= x:
if x % d == 0:
return False
d += 1
return True
Variables
x97dโ€”d * dโ€”x % dโ€”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
x
97
98
99
100
We ask: is ticket 97 prime? That is the call is_prime(97) โ€” no line has run yet.
1 / 28

The whole program. Write it in a new file, fast.py, and keep check_ticket.py.

python
def is_prime(x): d = 2 while d * d <= x: if x % d == 0: return False d += 1 return True tickets = [] with open("tickets-5.txt") as f: for line in f: tickets.append(int(line)) with open("out.txt", "w") as f: for x in tickets: if is_prime(x): f.write("YES\n") else: f.write("NO\n")
bash
python fast.py

How many checks now? A 12-digit ticket needs about 1,000,000 checks, read from the list above. Five tickets: about 5,000,000.

๐Ÿ… Section 8 โ€” New Requirement: 1,000,000 Tickets

The fair has one last idea: the grand draw. This time there are 1,000,000 tickets. No ticket number is above 1,000,000, and the same number can be on many tickets. The job is the same: write YES or NO for every ticket. At the end, also print how many tickets won. The judge still gives 1 second.

In fast.py, change the file name to "tickets-grand.txt" and run it. Wait. After a while, stop it with Ctrl+C.

One ticket near 1,000,000 needs about 1,000 checks, which is nothing. But 1,000 ร— 1,000,000 = 1,000,000,000 checks: about 100 seconds.

The map of primes

So work out every number from 0 to 1,000,000 once, before reading any ticket, and keep the answers in a list. Call it the map of primes: prime[x] says whether x is prime. After that, every ticket is one look-up. It is the same idea as sorting once in Binary Search: one big job at the start makes every question cheap.

x         0      1      2      3      4      5      6      7
prime[x]  False  False  True   True   False  True   False  True

How do we fill it? Calling is_prime on every number from 2 to 1,000,000 costs about 68,000,000 checks: about 7 seconds, before the first ticket is even read. Still too slow.

The trick is to stop asking "is this number prime?". Instead, take each prime and cross out its multiples. Whatever is never crossed out is prime.

Cross out the multiples
left = 100
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
The map for 1 to 100. Every number starts in. 1 is not prime, so it goes first.
1 / 15

Here is a way that works. The whole program, in a new file sieve.py:

python
def make_prime_map(limit): prime = [True] * (limit + 1) prime[0] = False prime[1] = False d = 2 while d * d <= limit: if prime[d]: m = d * d while m <= limit: prime[m] = False m += d d += 1 return prime prime = make_prime_map(1000000) tickets = [] with open("tickets-5.txt") as f: for line in f: tickets.append(int(line)) wins = 0 with open("out.txt", "w") as f: for x in tickets: if prime[x]: wins = wins + 1 f.write("YES\n") else: f.write("NO\n") print(wins)
bash
python sieve.py

Change the file name to "tickets-grand.txt" and run it again. It finishes in about half a second. Here is how the three ways compare:

โœ๏ธ Section 9 โ€” Exercises

Every exercise has its own file. Write each answer into out.txt, one line per input line. Like in a contest, every program must finish in about a second.

Homework