1845. Twin Prime Count
Twin primes are two primes that differ by exactly 2, such as 11 and 13 or 17 and 19. A researcher wants to know how many such pairs fit under a limit. Given n, count the pairs (p, p + 2) where both p and p + 2 are prime and p + 2 is not larger than n. The pairs (3, 5) and (5, 7) are different pairs, even though they share the prime 5.
Testing each number on its own is too slow when n is large. Mark the primes up to n with a sieve in one pass, then scan for neighbours that are 2 apart. Aim for O(n log log n) time and O(n) extra space.
Example 1
- Input:
- n = 20
- Output:
- 4
- Explanation:
The pairs are (3, 5), (5, 7), (11, 13) and (17, 19).
Example 2
- Input:
- n = 4
- Output:
- 0
- Explanation:
No pair fits under 4.
Example 3
- Input:
- n = 100
- Output:
- 8
- Explanation:
There are 8 pairs under 100.
Constraints
2 ≤ n ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log log n)
- Space
- O(n)