Solved Problem - Segmented Sieve

Problem statement

Given two integers, $N$ and $M$, print all primes between $N$ and $M$ (both inclusive).

Input format

The only line of input contains two integers $N$ and $M$ $(1 \leq N \leq M \leq 10^9)( M-N \leq 10^6)$.

---

Sample

Input

100000000 100000100

Output

100000007 100000037 100000039 100000049 100000073 100000081

---

Sieve

Obviously, Sieve of Eratosthenes comes to mind. Now, two things don’t work right here:

1. $M <= 10^9$, we don’t have enough memory to declare an array of a billion integers (4 GB memory).
2. Even if we could declare an array that big, the time complexity would be $O(M*log(logM))$, which is obviously very slow.

Observation: $M - N <= 10^6$

---

Segmented sieve

Since ...