Bài 17.2: Ứng dụng sàng số nguyên tố trong C++

Chào mừng bạn đến với chuỗi bài viết về C++ của FullhouseDev! Hôm nay, chúng ta sẽ cùng đi sâu vào một chủ đề thú vị và cực kỳ hữu ích trong lập trình: sàng số nguyên tố. Đặc biệt là sàng Eratosthenes, một thuật toán cổ điển nhưng vẫn giữ nguyên giá trị và được ứng dụng rộng rãi trong các bài toán liên quan đến số học.

Tại sao chúng ta lại cần sàng số nguyên tố? Khi làm việc với các số nguyên, việc xác định một số có phải là số nguyên tố hay không là một thao tác cơ bản. Nếu bạn chỉ cần kiểm tra cho một vài số riêng lẻ, các phương pháp thử chia đơn giản có thể chấp nhận được. Tuy nhiên, trong rất nhiều bài toán thực tế và các cuộc thi lập trình, bạn thường xuyên cần thực hiện các truy vấn kiểm tra số nguyên tố cho rất nhiều số trong một phạm vi nhất định, hoặc cần tìm tất cả các số nguyên tố trong phạm vi đó. Lúc này, việc kiểm tra từng số một sẽ trở nên cực kỳ tốn thời gian và kém hiệu quả.

Đây chính là lúc sàng số nguyên tố phát huy sức mạnh! Thay vì kiểm tra độc lập từng số, sàng số nguyên tố giúp chúng ta tính toán trước (precompute) thông tin về tính nguyên tố của tất cả các số trong một phạm vi đến một giới hạn $N$. Giống như việc "sàng" (lọc) các hợp số ra khỏi danh sách các số tự nhiên, chỉ để lại các số nguyên tố. Một khi quá trình sàng hoàn tất, việc kiểm tra tính nguyên tố của một số bất kỳ trong phạm vi $N$ chỉ tốn chi phí hằng số $O(1)$!

Thuật toán sàng kinh điển nhất là sàng Eratosthenes, được đặt theo tên của nhà toán học Hy Lạp cổ đại Eratosthenes xứ Cyrene. Ý tưởng cốt lõi rất đơn giản và trực quan.

Sàng Eratosthenes hoạt động như thế nào?

Hãy tưởng tượng chúng ta có một danh sách tất cả các số nguyên từ 2 đến $N$ và ban đầu, chúng ta giả định tất cả chúng đều là số nguyên tố.

  1. Bắt đầu với số nhỏ nhất là 2. Số 2 là số nguyên tố.
  2. Tất cả các bội số của 2 (lớn hơn 2) chắc chắn không phải là số nguyên tố (vì chúng chia hết cho 2). Chúng ta sẽ "đánh dấu" hoặc "loại bỏ" tất cả các bội số của 2: 4, 6, 8, 10, ... cho đến $N$.
  3. Di chuyển đến số tiếp theo trong danh sách mà chưa bị đánh dấu (chưa bị loại bỏ). Số đó là 3. Số 3 là số nguyên tố.
  4. Đánh dấu tất cả các bội số của 3 (lớn hơn 3) chưa bị đánh dấu: 6 (đã bị đánh dấu bởi 2), 9, 12 (đã bị đánh dấu), 15, ... cho đến $N$.
  5. Lặp lại quá trình này: Tìm số nhỏ nhất chưa bị đánh dấu, đó là số nguyên tố tiếp theo. Đánh dấu tất cả các bội số của nó.
  6. Chúng ta chỉ cần lặp lại bước 5 cho đến khi số nguyên tố hiện tại vượt quá căn bậc hai của $N$. Tại sao chỉ cần đến $\sqrt{N}$? Vì nếu một số $x > \sqrt{N}$ là hợp số, nó phải có ít nhất một ước số nguyên tố $p \le \sqrt{N}$. Khi chúng ta xử lý số nguyên tố $p$ trong quá trình sàng, hợp số $x$ sẽ bị đánh dấu thông qua $p$ (ví dụ $x = p \times k$, với $k \ge p$).
  7. Sau khi quá trình kết thúc, tất cả các số trong danh sách từ 2 đến $N$ mà chưa bị đánh dấu chính là các số nguyên tố.

Nghe có vẻ đơn giản đúng không? Bây giờ, hãy xem cách chúng ta có thể cài đặt nó trong C++.

Cài đặt Sàng Eratosthenes cơ bản trong C++

Chúng ta sẽ sử dụng một vector<bool> để lưu trữ trạng thái "là số nguyên tố" hoặc "không phải là số nguyên tố" cho mỗi số. vector<bool> là một dạng vector đặc biệt được tối ưu hóa bộ nhớ.

Giả sử chúng ta muốn sàng đến giới hạn N. Chúng ta cần một vector có kích thước N + 1 để lưu trữ thông tin cho các số từ 0 đến N.

#include <vector>
#include <iostream>
#include <cmath>

vector<bool> sang(int n) {
    vector<bool> nt(n + 1, true);
    nt[0] = nt[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (nt[i]) {
            for (int j = i * i; j <= n; j += i)
                nt[j] = false;
        }
    }
    return nt;
}

int main() {
    int g = 30;
    vector<bool> primes = sang(g);

    cout << "Danh sach tinh nguyen to den " << g << ":\n";
    for (int i = 0; i <= g; ++i) {
        cout << "So " << i << ": " << (primes[i] ? "Nguyen to" : "Khong nguyen to") << "\n";
    }

    return 0;
}

Output:

Danh sach tinh nguyen to den 30:
So 0: Khong nguyen to
So 1: Khong nguyen to
So 2: Nguyen to
So 3: Nguyen to
So 4: Khong nguyen to
So 5: Nguyen to
So 6: Khong nguyen to
So 7: Nguyen to
So 8: Khong nguyen to
So 9: Khong nguyen to
So 10: Khong nguyen to
So 11: Nguyen to
So 12: Khong nguyen to
So 13: Nguyen to
So 14: Khong nguyen to
So 15: Khong nguyen to
So 16: Khong nguyen to
So 17: Nguyen to
So 18: Khong nguyen to
So 19: Nguyen to
So 20: Khong nguyen to
So 21: Khong nguyen to
So 22: Khong nguyen to
So 23: Nguyen to
So 24: Khong nguyen to
So 25: Khong nguyen to
So 26: Khong nguyen to
So 27: Khong nguyen to
So 28: Khong nguyen to
So 29: Nguyen to
So 30: Khong nguyen to

Giải thích code:

  1. Chúng ta bao gồm các header cần thiết: <vector> cho vector, <iostream> cho nhập xuất, và <cmath> cho sqrt (mặc dù trong vòng lặp ta dùng p * p <= N thay vì p <= sqrt(N) để tránh phép toán dấu phẩy động, ý tưởng vẫn là lặp đến căn bậc hai).
  2. Hàm sieveEratosthenes(int N) nhận vào giới hạn trên N.
  3. vector<bool> isPrime(N + 1, true); tạo một vector boolean có kích thước N+1 và gán giá trị ban đầu là true cho tất cả các phần tử.
  4. isPrime[0] = isPrime[1] = false; đánh dấu rõ ràng 0 và 1 không phải là số nguyên tố.
  5. Vòng lặp ngoài for (int p = 2; p * p <= N; ++p) duyệt qua các số p bắt đầu từ 2. Chúng ta chỉ cần duyệt đến khi p*p vượt quá N (tương đương p > sqrt(N)).
  6. if (isPrime[p] == true) kiểm tra xem số p hiện tại có còn được xem là nguyên tố không. Nếu có, thì p chắc chắn là số nguyên tố (vì nó chưa bị đánh dấu bởi bất kỳ số nguyên tố nhỏ hơn nào).
  7. Vòng lặp trong for (int i = p * p; i <= N; i += p) duyệt qua các bội số của p, bắt đầu từ p*p.
    • Tại sao bắt đầu từ p*p? Các bội nhỏ hơn của p, ví dụ p*2, p*3, ..., p*(p-1), đã bị đánh dấu false bởi các số nguyên tố nhỏ hơn p (ví dụ, p*2 bị đánh dấu bởi 2, p*3 bị đánh dấu bởi 3, v.v.). Do đó, chúng ta có thể tiết kiệm thời gian bằng cách bắt đầu từ p*p.
    • i += p đảm bảo chúng ta chỉ xét các bội số của p.
  8. isPrime[i] = false; đánh dấu bội số i là không phải số nguyên tố.
  9. Sau khi vòng lặp ngoài kết thúc, vector isPrime đã chứa kết quả sàng. isPrime[i] sẽ là true nếu i là số nguyên tố (với $i \ge 2$) và false nếu i là hợp số, 0, hoặc 1.
Ứng dụng của Sàng Eratosthenes

Sàng Eratosthenes không chỉ giúp bạn hiểu về số nguyên tố mà còn là công cụ cực kỳ mạnh mẽ trong nhiều bài toán. Dưới đây là một vài ví dụ điển hình:

1. Kiểm tra tính nguyên tố của một số trong phạm vi đã sàng

Sau khi đã xây dựng sàng đến giới hạn $N$, việc kiểm tra xem một số $k \le N$ có phải là số nguyên tố hay không trở nên cực kỳ nhanh, chỉ là một thao tác truy cập mảng $O(1)$.

#include <vector>
#include <iostream>
#include <cmath>

vector<bool> sang(int n) {
    vector<bool> nt(n + 1, true);
    nt[0] = nt[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (nt[i]) {
            for (int j = i * i; j <= n; j += i)
                nt[j] = false;
        }
    }
    return nt;
}

bool la_nt(int x, int gh, const vector<bool>& nt) {
    if (x < 0 || x > gh) {
        cerr << "Loi: So " << x << " nam ngoai pham vi [" << 0 << ", " << gh << "]\n";
        return false;
    }
    return nt[x];
}

int main() {
    int gh = 100;
    vector<bool> nt_100 = sang(gh);

    cout << "Kiem tra tinh nguyen to trong pham vi [" << 0 << ", " << gh << "]:\n";
    cout << "So 2: " << (la_nt(2, gh, nt_100) ? "Nguyen to" : "Khong nguyen to") << "\n";
    cout << "So 10: " << (la_nt(10, gh, nt_100) ? "Nguyen to" : "Khong nguyen to") << "\n";
    cout << "So 17: " << (la_nt(17, gh, nt_100) ? "Nguyen to" : "Khong nguyen to") << "\n";
    cout << "So 99: " << (la_nt(99, gh, nt_100) ? "Nguyen to" : "Khong nguyen to") << "\n";
    cout << "So 101: " << (la_nt(101, gh, nt_100) ? "Nguyen to" : "Khong nguyen to") << "\n";

    return 0;
}

Output:

Kiem tra tinh nguyen to trong pham vi [0, 100]:
So 2: Nguyen to
So 10: Khong nguyen to
So 17: Nguyen to
So 99: Khong nguyen to
Loi: So 101 nam ngoai pham vi [0, 100]
So 101: Khong nguyen to

Giải thích code:

  1. Hàm isPrimeUsingSieve nhận số cần kiểm tra num, giới hạn tối đa đã sàng max_limit, và vector kết quả sàng isPrime_sieved.
  2. Đầu tiên, kiểm tra xem num có nằm trong phạm vi [0, max_limit] hay không. Nếu không, ta không có thông tin chính xác từ sàng và cần xử lý phù hợp (ở đây là in lỗi và trả về false).
  3. Nếu num nằm trong phạm vi, chỉ cần trả về giá trị tại isPrime_sieved[num]. Thao tác này là cực kỳ nhanh.
2. Liệt kê tất cả các số nguyên tố trong phạm vi đã sàng

Một ứng dụng phổ biến khác là liệt kê tất cả các số nguyên tố tìm được sau khi sàng.

#include <vector>
#include <iostream>
#include <cmath>

vector<bool> sang(int n) {
    vector<bool> nt(n + 1, true);
    nt[0] = nt[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (nt[i]) {
            for (int j = i * i; j <= n; j += i)
                nt[j] = false;
        }
    }
    return nt;
}

void liet_ke_nt(int gh, const vector<bool>& nt) {
    cout << "Cac so nguyen to trong pham vi [2, " << gh << "]:\n";
    for (int i = 2; i <= gh; ++i) {
        if (nt[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
}

int main() {
    int gh = 50;
    vector<bool> nt_50 = sang(gh);

    liet_ke_nt(gh, nt_50);

    return 0;
}

Output:

Cac so nguyen to trong pham vi [2, 50]:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Giải thích code:

  1. Hàm listPrimesUsingSieve nhận giới hạn max_limit và vector kết quả sàng.
  2. Chúng ta duyệt qua các số từ 2 đến max_limit.
  3. Với mỗi số i, nếu isPrime_sieved[i] là true, chúng ta in i ra màn hình.
3. Đếm số lượng số nguyên tố trong một phạm vi

Tương tự như liệt kê, chúng ta có thể dễ dàng đếm số lượng số nguyên tố.

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

vector<bool> sang(int n) {
    vector<bool> nt(n + 1, true);
    nt[0] = nt[1] = false;
    for (int i = 2; i * i <= n; ++i) {
        if (nt[i]) {
            for (int j = i * i; j <= n; j += i)
                nt[j] = false;
        }
    }
    return nt;
}

int dem_nt(int gh_dem, const vector<bool>& nt) {
    int gh_thuc = min(gh_dem, (int)nt.size() - 1);
    if (gh_dem < 2) return 0;

    int dem = 0;
    for (int i = 2; i <= gh_thuc; ++i) {
        if (nt[i]) {
            dem++;
        }
    }
    return dem;
}

int main() {
    int gh_sang = 100;
    vector<bool> nt_100 = sang(gh_sang);

    int dem_50 = dem_nt(50, nt_100);
    cout << "So luong so nguyen to den 50: " << dem_50 << "\n";

    int dem_100 = dem_nt(100, nt_100);
     cout << "So luong so nguyen to den 100: " << dem_100 << "\n";

    return 0;
}

Output:

So luong so nguyen to den 50: 15
So luong so nguyen to den 100: 25

Giải thích code:

  1. Hàm countPrimesUsingSieve nhận giới hạn đếm limit và vector kết quả sàng.
  2. Chúng ta giới hạn actual_limit để không vượt quá kích thước của vector sàng.
  3. Duyệt từ 2 đến actual_limit và tăng biến đếm count nếu số đó là nguyên tố dựa trên kết quả sàng.
Hiệu quả của Sàng Eratosthenes

Sàng Eratosthenes có độ phức tạp thời gian là O(N log log N), đây là một hiệu suất rất tốt cho việc tìm kiếm tất cả các số nguyên tố đến $N$. Độ phức tạp bộ nhớ là O(N) để lưu trữ vector isPrime.

Đối với các bài toán yêu cầu nhiều truy vấn kiểm tra hoặc liệt kê số nguyên tố trong một phạm vi cố định, chi phí xây dựng sàng ban đầu là hoàn toàn xứng đáng vì mỗi truy vấn sau đó là cực kỳ nhanh. Nếu bạn chỉ cần kiểm tra tính nguyên tố của một hoặc hai số rất lớn (ngoài phạm vi sàng), thì các thuật toán kiểm tra nguyên tố chuyên biệt khác như kiểm tra Miller-Rabin sẽ phù hợp hơn. Nhưng trong phạm vi nhỏ hơn (thường là đến $10^6$ hoặc $10^7$ trong các cuộc thi lập trình), sàng Eratosthenes là lựa chọn hàng đầu.

Các ứng dụng nâng cao khác

Khái niệm sàng số nguyên tố còn là nền tảng cho nhiều thuật toán số học khác:

  • Sàng phân tích thừa số nguyên tố nhỏ nhất (SPF Sieve): Một biến thể của sàng Eratosthenes không chỉ đánh dấu hợp số mà còn lưu lại ước số nguyên tố nhỏ nhất của mỗi hợp số. Điều này cho phép phân tích thừa số nguyên tố của bất kỳ số nào đến $N$ trong thời gian logarit $O(\log N)$ sau khi sàng.
  • Tính hàm số học: Sàng có thể được mở rộng để tính các hàm số học như hàm Mobius ($\mu$), hàm tổng ước (sigma, $\sigma$), hàm số lượng ước ($\tau$), hoặc hàm Euler Totient ($\phi$) cho tất cả các số đến $N$ một cách hiệu quả.

Như bạn thấy, sàng số nguyên tố không chỉ là một bài tập lý thuyết mà là một công cụ sắc bén trong "hộp đồ nghề" của lập trình viên, đặc biệt khi giải quyết các bài toán về số học và tối ưu hóa hiệu suất.

Comments

There are no comments at the moment.