8857: [yosupo] Number Theory - Enumerate Primes
[Creator : ]
Description
Let the prime numbers be $p_0 < p_1 < p_2 < \cdots$ (i.e. $p_0 = 2$, $p_1 = 3$, $p_2 = 5$, and so on).
You are given integers $N$, $A$ and $B$.
Find $\pi(N)$ (the number of primes no greater than $N$),
and print $p_{Ai+B}$ for nonnegative integers $i$ with $p_{Ai+B} \le N$.
You are given integers $N$, $A$ and $B$.
Find $\pi(N)$ (the number of primes no greater than $N$),
and print $p_{Ai+B}$ for nonnegative integers $i$ with $p_{Ai+B} \le N$.
Input
$N$ $A$ $B$
Constraints
- $1 \le N \le 500,000,000$
- $0 \le B < A \le N$
- $0 \le X \le 10^{16}$ where $X = \#\ \{ i \in \mathbb{Z}\_{\ge 0} \mid p_{Ai+B} \le N \}$
- $0 \le B < A \le N$
- $0 \le X \le 10^{16}$ where $X = \#\ \{ i \in \mathbb{Z}\_{\ge 0} \mid p_{Ai+B} \le N \}$
Sample 1 Input
100 3 1
Sample 1 Output
25 8
3 11 19 31 43 59 71 83