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.
- tickets-5.txt โ 5 tickets, one number per line:
7 51 97 12 89.
Try it first
You already know everything you need: read the file, and for each ticket try every number from 2 to x - 1. x % d is the remainder, so x % d == 0 means d divides x. Write the program yourself before you open the answer.
Save it as check_ticket.cpp, then compile and run it:
bashg++ -o check_ticket check_ticket.cpp ./check_ticket
Your out.txt should be exactly this:
YES
NO
YES
NO
YESThis 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 200,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.
Download the data
tickets-region-cpp.txt โ 5 tickets up to 200,000,000.
tickets-country.txt โ 5 tickets up to 1,000,000,000,000.
- In your program, change
"tickets-5.txt"to"tickets-region-cpp.txt". Save, compile withg++again, and run./check_ticket. It finishes โ but you have to wait. - Before the country file, the program needs a bigger number type.
A new type: long long
An
intholds numbers up to about 2,000,000,000 (2 ร 10โน). A 12-digit ticket does not fit. Along longholds numbers up to about 9 ร 10ยนโธ.The rule: every variable that holds a ticket, or something as big as a ticket, becomes
long long. Change these four lines, and the file name:vector<int> tickets;becomesvector<long long> tickets;int t;becomeslong long t;for (int x : tickets)becomesfor (long long x : tickets)for (int d = 2; d < x; d++)becomesfor (long long d = 2; d < x; d++), becausedclimbs as high as the ticket."tickets-region-cpp.txt"becomes"tickets-country.txt"
The whole program now:
cpp#include <iostream> #include <fstream> #include <vector> using namespace std; int main() { ifstream fin("tickets-country.txt"); vector<long long> tickets; long long t; while (fin >> t) { tickets.push_back(t); } ofstream fout("out.txt"); for (long long x : tickets) { bool found = false; for (long long d = 2; d < x; d++) { if (x % d == 0) { found = true; } } if (found) { fout << "NO" << endl; } else { fout << "YES" << endl; } } return 0; } - Save, compile 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.
Now make the program count its own work: add long long steps = 0; at the start of main, add 1 every time it tries a divisor, and print steps at the end. The counter is long long too: 1,000,000,000 is close to the int limit, and the country file goes far past it.
cpp#include <iostream> #include <fstream> #include <vector> using namespace std; int main() { long long steps = 0; ifstream fin("tickets-5.txt"); vector<long long> tickets; long long t; while (fin >> t) { tickets.push_back(t); } ofstream fout("out.txt"); for (long long x : tickets) { bool found = false; for (long long d = 2; d < x; d++) { steps = steps + 1; if (x % d == 0) { found = true; } } if (found) { fout << "NO" << endl; } else { fout << "YES" << endl; } } cout << steps << endl; return 0; }
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:
- 5 tickets up to 100: 246 steps.
- 5 tickets up to 200,000,000: about 1,000,000,000 steps โ the wait you just had.
- 5 tickets up to 1,000,000,000,000: about 5,000,000,000,000 steps.
Estimate before you code
The rule from last lesson: C++ does about 100 million simple steps per second. So by the rule, 1,000,000,000 steps take about 10 seconds. And 5,000,000,000,000 steps take about 50,000 seconds โ more than half a day. The program is right, but the judge gives it 1 second.
๐งฉ 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.
The problem
We need to check far fewer divisors, and still be sure of the answer.
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.
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.
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.
Half is still too slow
That cuts the work in half. But half of 5,000,000,000,000 steps is still 2,500,000,000,000: about 25,000 seconds, about 7 hours. Look at the pairs again. Can we stop even earlier?
๐ Section 7 โ isPrime
Half way came from the biggest possible divisor. Now look at both sides of the pairs together.
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?
- Ticket 100: up to 10.
- Ticket 10,000: up to 100.
- Ticket 1,000,000: up to 1,000.
- Ticket 1,000,000,000,000: up to 1,000,000.
The idea, written as a function:
dis the divisor being tried. It starts at 2 and goes up by 1.- The loop runs while
d * d <= x. Past that,dis beyond the middle. - If
ddividesx, we know the answer at once:return false, the same earlyreturnascontains. - If the loop ends with no divisor found,
xis prime.
Watch it on two tickets: 97, which is prime, and 91, which is not. The buttons under the picture switch between them.
That is the idea. Here is the same check written as code โ a function we call isPrime. 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.
isPrime(97) โ no line has run yet.The whole program. Write it in a new file, fast.cpp, and keep check_ticket.cpp.
cpp#include <iostream> #include <fstream> #include <vector> using namespace std; bool isPrime(long long x) { for (long long d = 2; d * d <= x; d++) { if (x % d == 0) return false; } return true; } int main() { ifstream fin("tickets-5.txt"); vector<long long> tickets; long long t; while (fin >> t) { tickets.push_back(t); } ofstream fout("out.txt"); for (long long x : tickets) { if (isPrime(x)) { fout << "YES\n"; } else { fout << "NO\n"; } } return 0; }
dislong longtoo, becaused * dreaches 1,000,000,000,000, which does not fit in anint. It is the same rule as the ticket: anything as big as a ticket islong long.
bashg++ -o fast fast.cpp ./fast
Build one piece, then test it
Run it on the small file first: out.txt must be the same YES NO YES NO YES as in Section 1. Then the region file. Then the country file that got stuck in Section 2 โ it now finishes almost instantly.
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.
Download the data
tickets-grand.txt โ 1,000,000 tickets up to 1,000,000.
In fast.cpp, change the file name to "tickets-grand.txt" and run it. It takes seconds, not 1 second.
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 10 seconds.
The problem
In Section 2, one ticket was too slow. Now each ticket is quick and there are just too many of them. And the program keeps repeating itself: every time the same number comes up, it works out the answer from the beginning.
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 vector. 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 trueHow do we fill it? Calling isPrime on every number from 2 to 1,000,000 costs about 68,000,000 checks: about 0.7 seconds, nearly all of our second gone before the first ticket is even read. We can do much better.
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.
- Start at d ร d. Smaller multiples of
d, like 2 ร d or 3 ร d, were already crossed out by 2 and 3. - Stop when d ร d passes the limit. It is the same reason as in Section 7: every number that is not prime has a divisor up to its middle, so it is crossed out by then.
- This method has a name: the Sieve of Eratosthenes. A sieve lets the small bits fall through; here, the primes are what stays.
Try it first
Write a program that builds the map, then looks up every ticket. Do not read on until you have tried.
On tickets-5.txt, out.txt should be YES NO YES NO YES and your program should print 3. On tickets-grand.txt it should print exactly 506846.
Here is a way that works. The whole program, in a new file sieve.cpp:
cpp#include <iostream> #include <fstream> #include <vector> using namespace std; vector<bool> makePrimeMap(int limit) { vector<bool> prime(limit + 1, true); prime[0] = false; prime[1] = false; for (int d = 2; d * d <= limit; d++) { if (prime[d]) { for (int m = d * d; m <= limit; m += d) { prime[m] = false; } } } return prime; } int main() { vector<bool> prime = makePrimeMap(1000000); ifstream fin("tickets-5.txt"); vector<int> tickets; int t; while (fin >> t) { tickets.push_back(t); } int wins = 0; ofstream fout("out.txt"); for (int x : tickets) { if (prime[x]) { wins = wins + 1; fout << "YES\n"; } else { fout << "NO\n"; } } cout << wins << endl; return 0; }
bashg++ -o sieve sieve.cpp ./sieve
vector<bool> prime(limit + 1, true)makes a vector oflimit + 1values, alltrue. The+ 1is there because a vector starts at position 0, and we need position 1,000,000 too.prime[0]andprime[1]are set by hand: neither is prime, and no crossing out would ever reach them.if (prime[d])skips a number that is already crossed out.m += djumps straight to the next multiple, so no division is needed.- No ticket here is above 1,000,000, and neither is
d * dby much, sointis enough.
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:
- isPrime on every ticket: about 1,000,000,000 checks
- isPrime to fill the map: about 68,000,000 checks
- Crossing out to fill the map: about 2,100,000 crossings, plus one look-up per ticket
Which tool when
- A few huge numbers, up to 1,000,000,000,000: use
isPrime. A map that long would not fit in the computer's memory. - Many numbers, up to about 1,000,000: build the map once.
โ๏ธ 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.
- For each
x(up to 1,000,000,000,000), writeYESifxis a perfect square: some whole number times itself. OtherwiseNO. ex1.txt - Read
N(20,000 in this file) and write how many primes there are from 1 toN. The answer must be exactly2262. ex2.txt - For each
x(up to 1,000,000,000,000), write how many divisorsxhas. ex3.txt - Twin primes are two primes that differ by exactly 2, like 11 and 13. Read
N(1,000,000 in this file) and write how many pairs of twin primes there are from 1 toN. The answer must be exactly8169. ex4.txt - For each
x(up to 1,000,000,000,000), write the smallest prime that is at leastx. ex5.txt - For each
x, writeYESif the sum of its digits is prime. OtherwiseNO. ex6.txt - Two-ticket draw: every line has one even number
x, from 4 to 1,000,000. Two primes must add up tox. Write the smallest prime that can be one of the two: for 10, write3, because 3 + 7 = 10. ex7.txt
Homework
- For each
x(up to 1,000,000,000,000), writeYESifxhas exactly 3 divisors. OtherwiseNO. ex8.txt