Primes in a window
A key generator sieves windows of numbers far from zero and looks for primes in them. To check it, a reference is needed: for each window [L, R], how many primes it has and what the widest gap between neighbouring primes inside the window is. A gap is the difference of two neighbouring primes: between 23 and 29 it is 6.
Input
The first line holds the number of windows q (1 ≤ q ≤ 5). Each of the next q lines holds two integers L and R (1 ≤ L ≤ R ≤ 10¹², R − L ≤ 10⁶). Both ends belong to the window.
Output
For each window, on a separate line, two numbers: the number of primes in the window and the largest difference of neighbouring primes from this window. If there are fewer than two primes in the window, print 0 as the second number.
Examples
Example 1
4 1 30 90 100 1 1 97 97
10 6 1 0 0 0 1 0
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Checking each number of the window with divisors up to the root is up to a million divisions per number, and there are a million numbers in a window. How much is that over five windows?
2Hint 2
Any composite number up to 10¹² has a prime divisor no greater than 10⁶. Which primes are needed to cross out all the composites in a window, and how many are there?
3The idea
This is the segmented sieve. Find the primes up to √R ≤ 10⁶ with an ordinary sieve: there are 78,498 of them. Then for each window keep an array of flags of length R − L + 1 and with each prime p cross out its multiples inside the window. What remains are primes; count them and the gaps.
4Walkthrough
The first multiple of p in the window is ⌈L/p⌉ · p = (L + p − 1) / p · p in integers. But start no earlier than p²: otherwise, in a window that takes in small numbers, the sieve crosses out the prime p itself. Cross out one separately if it is in the window.
Count the gaps in one pass over the window: remember the position of the previous prime and update the maximum difference. In Python it is convenient to find the next one in the flags with bytearray.find: it runs in C, and a pass over a million flags is almost free. Crossing out is a slice too: win[start - L :: p] = bytes(cnt).
The second test holds a real record: after the prime 738,832,927,927 the next prime is 540 away. That is the widest gap between primes up to 10¹² (sequence A002386 in the OEIS).
4+Solution
5Complexity
The primes up to √R: O(√R log log R). For each window of length w: O(w log log R + π(√R)), the crossings plus one check per prime, even if it has no multiples in the window. Memory is O(√R + w). Trial division would cost O(w√R) per window, hundreds of thousands of times more.
6Common mistakes
- Each number separately. Trial division up to the root for a million numbers around 10¹² will not fit in any time.
- A sieve from zero to R. An array of 10¹² flags is a terabyte.
- One and small primes. In a window starting at 1, one is not prime while 2, 3, 5 are; if crossing out starts at the first multiple in the window rather than at p², they disappear. The third test is the window [1, 10⁶], which should give 78,498.
- Overflow.
p * pand L + p up to 10¹² do not fit in 32 bits.