Where it runs
1. The problem
A prime is a number bigger than 1 that divides only by 1 and by itself: 2, 3, 5, 7, 11. You need all the primes up to a million, and you need them fast.
The obvious way is to test each number on its own. Is 91 prime? Try dividing it by 2, 3, 4 and on, up to the square root of 91 (about 9.5). It divides by 7: 91 = 7 · 13, so it is not prime. For one number that is quick. Repeat the test for a million numbers and you get a million separate searches, with the same divisions done again and again.
There is a way to find every prime in a range in almost one pass. Instead of testing each candidate, you cross out the numbers that cannot be prime.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- reduce a fraction to lowest terms
- list all primes up to n
- answer modulo 1e9+7
- when do two repeating intervals line up again (LCM)
Looks similar, isn't
- Bit manipulation
Both work on the number itself. That page is about the individual bits.
- Hash set / map
A set of primes still has to be built somehow. A sieve is how you build it.
- Dynamic programming (1-D)
A formula answers at once where DP fills a table. Look for a closed form first.
- Prefix sums
Prefix sums answer over values that were stored. Here the answer comes from the numbers themselves.
GCD costs O(log of the smaller value). A sieve up to 1e7 is fine, but 1e9 is not.
On LeetCode
Problems that need every prime up to some limit, such as counting primes or finding prime pairs in a range. The sieve crosses out multiples starting at p^2 and answers in O(n log log n).
Sieve below n and count the trues. n is up to 5 * 10^6, so testing each number on its own is too slow.
Count the primes up to n with the sieve, then multiply the factorials of the prime count and of the rest, modulo 10^9 + 7.
Sieve up to right, walk the primes between left and right, and keep the pair with the smallest gap.
Sieve up to n, then for each prime x up to n / 2 check whether n minus x is prime too.