Hướng dẫn cho Tìm số nguyên tố


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


\(\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}}}}\)

C++
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;
}


Bình luận


  • 0
    lagiahuy    10:47 a.m. 20 Tháng 10, 2021

    cho mình hỏi là làm editorial thế nào vậy?