\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

• Duyệt qua và kiểm tra nếu số nào là nguyên tố thì in ra

Có thể cải tiến bằng cách chỉ duyệt đến \(O(\sqrt x)\) để kiểm tra \(x\) có nguyên tố hay không

Có thể cải tiến bằng cách duyệt các số có dạng \(6 \times k \pm 1\)

\(\color{orange}{\text{Hint 2 <Sieving>}}\)

• Sử dụng sàng nguyên tố để lọc ra các số nguyên tố và xuất ra các số đó

Sàng nguyên tố là với mỗi số từ \(2\) trở lên mà chưa bị đánh dấu ta đánh dấu các bội của nó. Những số vẫn chưa bị đánh dấu chính là số nguyên tố

Cải tiến bằng cách sử dụng \(lpf[x]\) là ước nguyên tố nhỏ nhất của \(x\) để tính toán trong thời gian tuyến tính

\(\color{orange}{\text{Hint 3 <Implementation>}}\)

• Sau khi sàng, việc duyệt sẽ tốn thời gian nên ta sẽ dùng mảng nguyên tố \(prime[]\) và duyệt xem có bao nhiêu số trong đoạn thì xuất hết ra

Có thể cải tiến việc chặt nhị phân tìm phần tử đầu nằm trong đoạn và xuất hết tới khi số nguyên tố đang xét không còn trong đoạn

\(\color{green}{\text{Preference AC Code }}\): Sieving

\(^{^{\color{purple}{\text{Complexity : }} O(r)\ \color{purple}{\text{time}}\ ||\ O(r)\ \color{purple}{\text{memory}}}}\)

vector<int> prime, lpf;
void sieve(int lim = LIM)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    for (int i = 3; i <= lim; i += 2)
    {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(prime) && prime[j] <= lpf[i] && i * prime[j] <= lim; ++j)
            lpf[i * prime[j]] = prime[j];
    }
}

int main()
{
    cin >> l >> r;
    sieve(r + 500);

    int p = lower_bound(all(prime), l) - prime.begin();
    while (prime[p] <= r) cout << prime[p++] << '\n';
    return 0;
}