Hướng dẫn cho Đế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{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}$

$\color{#ff0000}{\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{#ff0000}{\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{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}$ ở đây

$\color{#300000}{\text{Hint 1 <Cày trâu>}}$

Với mỗi truy vấn $l, r$ ta sẽ duyệt qua đoạn $l, r$ và kiểm tra xem có bao nhiêu số nguyên tố
Việc kiểm tra có thể dùng thuật toán $miller-rabin$ trong $O(polylog(p)) \approx O(log^4(p))$ hoặc duyệt $O(\sqrt{p})$
Gọi $O(query())$ là độ phức tạp trả lời truy vấn, $O(check())$ là độ phức tạp hàm kiểm tra
Độ phức tạp thời gian tổng thể cách này sẽ là $O(q) \times O(query(max\_val)) \times O(check(max\_val))$

$\color{#300000}{\text{Hint 2 <Tiền xử lí>}}$

Mình sẽ tiền xử lí đánh dấu các số nguyên tố, lúc này ta có thể kiểm tra các số nguyên tố trong $O(1)$
Gọi $O(precal())$ là độ phức tạp hàm tiền xử lí
Độ phức tạp thời gian tổng thể của cách này sẽ là $O(q) \times O(query(max\_val)) \times O(1) + O(precal(max\_val))$

$\color{#300000}{\text{Hint 3 <Sàng nguyên tố>}}$

Cách đánh dấu cơ bản là mình duyệt từng số $x$ trong đoạn $[1, max\_val]$ và kiểm tra xem nếu nó chỉ có 2 ước $d$ nguyên dương là $d_1 = 1$ và $d_2 = x$

Cách này có độ phức tạp là $O(precal()) = O(max\_val \times O(check())$

$\rightarrow$ Độ phức tạp tổng thể $O(q \times max\_val \times O(1) + max\_val \times O(check()) = O(max\_val \times (q + O(check()))$

Thay vì thử tìm các ước, ta sẽ thử đánh dấu các bội, có nghĩa là với mỗi số nguyên tố, ta sẽ đánh dấu tất cả bội của nó sẽ không còn là số nguyên tố nữa

Chứng minh: Gọi $p$ là số nguyên tố đang xét, thì các bội của nó $x \times p$ với $(x \in \mathbb{N^*}, x > 1)$ sẽ có ít nhất 3 ước $d$ là $\{1, p, x \times p\}$ nên sẽ không phải là số nguyên tố

Ta sẽ không cần đánh dấu các bội của số nguyên tố quá giá trị $max\_val$

Chứng minh: mình chỉ cần đánh dấu các bội trong khoảng $[1, max\_val]$, những số lớn hơn không ảnh hưởng tới việc đánh dấu (vì bội của các số đang xét luôn lớn hơn chính nó nên không có trường hợp mình xét các số nhỏ hơn)

Trong quá trình duyệt từ số nguyên tố $p = 2 \rightarrow max\_val$, những số chưa bị đánh dấu sẽ là số nguyên tố

Chứng minh: Nếu $p$ chưa bị đánh dấu thì $p$ không có ước nguyên tố nào trong đoạn $[2, p - 1]$ nên $p$ chỉ có duy nhất 2 ước nguyên dương là $\{1, p\}$ $\Rightarrow$ $p$ là số nguyên tố

Mỗi lần duyệt một số $p$, chi phí để duyệt qua bội của nó là $O(\frac{n}{p})$ với $p$ nguyên tố và $O(1)$ với $p$ hợp số nên $O(precal()) = O(n \log \log n)$

Chứng minh: (cp-algorithms), link tới chứng minh cụ thể hơn - p349

Có $O(precal()) = O(n) + O(\frac{n}{2} + \frac{n}{3} + \frac{n}{5} + \frac{n}{7} + \dots) = O(n) + O(n) \times O(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots)$

Mà $\frac{1}{3} + \frac{1}{5} + \frac{1}{7} + \dots = \underset{\underset{\text{prime p}}{p \leq n}}{\Sigma}\frac{1}{p} \approx \sum_{k = 2}^{\frac n {\ln n}} \frac 1 {k \ln k} \approx \int_2^{\frac n {\ln n}} \frac 1 {k \ln k} dk =\ln \ln \frac n {\ln n} - \ln \ln 2 = \ln(\ln n - \ln \ln n) - \ln \ln 2 \approx \ln \ln n$

Nên ta có $O(precal()) = O(n) + O(n) \times O(\frac{1}{2} + \ln \ln n) = O(n \log \log n)$

Độ phức tạp thơi gian tổng thể là $O(q) \times O(query(max\_val)) + O(n \log \log n)$

$\color{#300000}{\text{Hint 4 <Chặt nhị phân>}}$

Gọi $prime[]$ là danh sách các số nguyên tố sắp xếp tăng dần sau khi sàng, mình cần trả lời $q$ truy vấn đếm số nguyên tố trong đoạn $[l, r]$

Khi $l > r$ thì kết quả là $0$, ngược lại ta có:

Gọi vị trí số nguyên tố nhỏ nhất lớn hơn $l$ là $p_1$

Gọi vị trí số nguyên tố nhỏ nhất lớn hơn $r$ là $p_2$ $\Rightarrow$ vị trí số nguyên tố lớn nhất nhỏ hơn $r$ là $p_2 - 1$

$\Rightarrow$ số nguyên tố trong đoạn $l, r$ là $(p_2 - 1) - p_1 + 1 = p_2 - p_1$

Việc chặt nhị phân mất $O(query()) = O(\log_2 (prime.size)) = O(\log_2(\frac{n}{\ln{n}}))$
Độ phức tạp thơi gian tổng thể là $O(q) \times O(\log_2(\frac{n}{\ln{n}})) + O(n \log \log n)$

$\color{#300000}{\text{Hint 5 <Quy hoạch động>}}$

Gọi $f[0..n]$ là số lượng số nguyên tố trong đoạn $[0..n]$

$\Rightarrow$ số lượng số nguyên tố trong đoạn $[l..r]$ là $f[l..r] = f[0..r] - f[0..l - 1]$

Ta sẽ trả lời truy vấn $O(query()) = O(1)$ nhưng sẽ mất $O(n)$ bộ nhớ

Công thức quy hoạch động:

$f[0..x] = 0$ với $x \leq 1$

$f[0..x] = f[x - 1] + 1$ với $x$ nguyên tố

$f[0..x] = f[x - 1] + 0$ với $x$ hợp số

Độ phức tạp thơi gian tổng thể là $O(q) + O(n \log \log n)$

$\color{#300000}{\text{Hint 6 <Tối ưu hóa>::<Constant Optimization>}}$

Viêc tối ưu hóa hằng số có thể giúp nó nhanh lên rất nhiều lần và tất cả những cải tiến dưới đây có thể gộp vào 1

Chỉ duyệt các số lẻ từ $p = 3$ sau khi các số chẵn ngoại trừ số $2$ sẽ được đánh dấu trước

Chứng minh: Tất cả số chẵn đều là bội của $2$, mà $2$ là số nguyên tố chẵn duy nhất nên các số nguyên tố còn lại đều lẻ

Khi $p^2 > n$ thì không cần xét và $break$ ngay

Chứng minh: Nếu $p^2 > n$ thì $(p + x)^2 > n\ (\forall x \in \mathbb{N})$ mà ta chỉ đang đánh dấu các số nguyên tố trong đoạn $[1, n]$

Thay vì kiểm tra $p^2 \leq n$ ta cũng có thể kiểm tra $p \leq sqrtn$ với $sqrtn = \sqrt{n}$ đã được tính trước và không cần tính lại

Chứng minh: Việc tính đi tính lại $p^2$ trong $n$ lần chậm hơn là 1 lần tính $\sqrt{n}$ và kiểm tra $p \leq sqrtn$ trong $n$ lần

Thay vì duyệt các bội $p$ từ $2p, 3p, \dots$ thì ta sẽ duyệt từ $p \times p, (p + 2) \times p, (p + 4) \times p$

Chứng minh:

Các số có dạng $(p + 2k + 1) \times p$ là số chẵn và đã được đánh dấu là bội của $p_0 = 2$

Các số từ $2p \dots (p - 1)$ đã được đánh dấu bởi các số nguyên tố nhỏ hơn $p$

Chúng ta không cần sắp xếp lại mảng số nguyên tố mà có thể duyệt các giá trị từ nhỏ đến lớn và kiểm tra tính nguyên tố rồi chèn vào

$\color{#300000}{\text{Hint 7 <Tối ưu hóa>::<Time Optimization>}}$

Chúng ta có thể giảm độ phức tạp lí thuyết xuống thời gian tuyến tính

Gọi $prime[]$ là danh sách các số nguyên tố và $lpf[x]$ là ước nguyên tố nhỏ nhất của $x$ thì mình chỉ cần duyệt qua các $prime[i] \times p$ thỏa ($prime[i] \times p \leq n$ và $prime[i] \leq lpf[p]$)

Chứng minh:

Nếu $prime[i] \times p > n$ thì không cần xét

Nếu $prime[i] > lpf[p]$ thì nó sẽ làm các số bị duyệt trùng

Chúng ta có thể sàng trên từng đoạn $O(\sqrt n)$ để sàng nhanh hơn và dùng bitwise để đẩy nhanh tốc độ tính toán bằng cách sàng từng đoạn $O(\sqrt n) \approx O(2^15) \approx O(CPU\_cache)$

$\color{#300000}{\text{Hint 8 <Tối ưu hóa>::<Space Optimization>}}$

Việc dùng mảng boolean rất lãng phí trong C++ vì nó chỉ lưu 2 trạng thái $\{0, 1\}$ trong khi nó lưu trữ 1 byte (= 8 bit = $2^8$ trạng thái)$
Chúng ta có thể dùng bitset<size> hoặc std::vector<bool> hoặc unsigned int array[] để đánh dấu các số với độ phức tạp $O(\frac{n}{8})$ bằng bitwise. Vì lúc này ta tận dụng hiệu quả đến từng bit
Chúng ta có thể giảm một nửa mảng đánh dấu bằng việc chuyển giá trị $[x]$ lưu vào $[\lfloor \frac{x}{2} \rfloor]$

$2$ và $3$ là 2 số nguyên tố lưu chung vào $[1]$

Những số chẵn khác 2 đều không phải số nguyên tố

Những số lẻ $p$ có $isPrime[\frac{p - 1}{2}] = \{0, 1\}$ là $\{$hợp số, số nguyên tố$\}$

Chúng ta có thể sàng trên từng đoạn $O(\sqrt n)$ với $O(\sqrt n)$ bộ nhớ chính, $O(\frac{n}{ln n})$ để lưu số nguyên tố

$\color{#009933}{\text{Preference Accepted Code }}$: Thao tác bit, Sàng nguyên tố, Tiền xử lí, Giải trực tiếp

$^{^{\color{#7f5f3f}{\text{Complexity : }} O(n + q)\ \color{#7f5f3f}{\text{time}}\ ||\ O(\frac{n}{64})\ \color{#7f5f3f}{\text{memory}}}}$

C++

const int LIM = 2e8;
bitset<LIM> isPrime;
vector<int> prime;
void sieve(int n = LIM)
{
    isPrime[2] = true;
    prime.assign(1, 2);

    int sqrtn = sqrt(n);
    for (int i = 3; i <= n; i += 2) isPrime.set(i);
    for (int i = 3; i <= n; i += 2)
    {
        if (isPrime[i])
        {
            prime.push_back(i);
            if (i > sqrtn) continue;
            for (int j = i * i; j <= n; j += 2 * i)
                isPrime.reset(j);
        }
    }
}

int main()
{
    sieve();

    int q;
    for (cin >> q; q--; )
    {
        int l, r;
        cin >> l >> r;

        if (l > r)
        {
            cout << 0 << '\n';
            continue;
        }
        int p1 = lower_bound(prime.begin(), prime.end(), l) - prime.begin();
        int p2 = upper_bound(prime.begin(), prime.end(), r) - prime.begin();
        cout << p2 - p1 << '\n';
    }
    return 0;
}

Bình luận

0

mt12345 9:10 p.m. 7 Tháng 3, 2023

Cái này có sàng được đến 1e9 mà không bị quá bộ nhớ k nhỉ?

5 bình luận nữa

Hướng dẫn cho Đếm số nguyên tố

\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\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{#ff0000}{\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{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

\(\color{#300000}{\text{Hint 2 <Tiền xử lí>}}\)

\(\color{#300000}{\text{Hint 3 <Sàng nguyên tố>}}\)

\(\color{#300000}{\text{Hint 4 <Chặt nhị phân>}}\)

\(\color{#300000}{\text{Hint 5 <Quy hoạch động>}}\)

\(\color{#300000}{\text{Hint 6 <Tối ưu hóa>::<Constant Optimization>}}\)

\(\color{#300000}{\text{Hint 7 <Tối ưu hóa>::<Time Optimization>}}\)

\(\color{#300000}{\text{Hint 8 <Tối ưu hóa>::<Space Optimization>}}\)

\(\color{#009933}{\text{Preference Accepted Code }}\): Thao tác bit, Sàng nguyên tố, Tiền xử lí, Giải trực tiếp

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n + q)\ \color{#7f5f3f}{\text{time}}\ ||\ O(\frac{n}{64})\ \color{#7f5f3f}{\text{memory}}}}\)

Bình luận