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> // Cần cho sqrt

// Hàm thực hiện sàng Eratosthenes
vector<bool> sieveEratosthenes(int N) {
    // Khởi tạo vector 'isPrime' có kích thước N + 1.
    // Ban đầu, giả định tất cả các số từ 0 đến N đều là nguyên tố.
    vector<bool> isPrime(N + 1, true);

    // Số 0 và 1 không phải là số nguyên tố.
    isPrime[0] = isPrime[1] = false;

    // Bắt đầu từ p = 2. Lặp cho đến căn bậc hai của N.
    // Nếu p vẫn được đánh dấu là nguyên tố (isPrime[p] == true)...
    for (int p = 2; p * p <= N; ++p) {
        if (isPrime[p] == true) {
            // ...thì đánh dấu tất cả các bội số của p (lớn hơn p)
            // là không phải số nguyên tố.
            // Bắt đầu từ p*p vì các bội nhỏ hơn (p*2, p*3, ...) đã
            // được đánh dấu bởi các số nguyên tố nhỏ hơn.
            for (int i = p * p; i <= N; i += p)
                isPrime[i] = false;
        }
    }

    // Trả về vector chứa thông tin về tính nguyên tố.
    return isPrime;
}

/*
int main() {
    int limit = 30; // Ví dụ: Sàng đến 30
    vector<bool> primes = sieveEratosthenes(limit);

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

    return 0;
}
*/

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>

// (Giả định hàm sieveEratosthenes từ ví dụ trước đã tồn tại hoặc được gọi)
// vector<bool> isPrime_global = sieveEratosthenes(MAX_LIMIT);

// Hàm kiểm tra nguyên tố sử dụng kết quả sàng
bool isPrimeUsingSieve(int num, int max_limit, const vector<bool>& isPrime_sieved) {
    // Kiểm tra số âm hoặc lớn hơn giới hạn đã sàng
    if (num < 0 || num > max_limit) {
        // Xử lý số ngoài phạm vi: có thể kiểm tra riêng hoặc báo lỗi
        cerr << "Error: Number " << num << " is outside the sieved range [0, " << max_limit << "]\n";
        return false; // Hoặc bạn có thể triển khai kiểm tra riêng ở đây
    }
    // Kiểm tra trực tiếp dựa vào kết quả sàng
    return isPrime_sieved[num];
}

/*
int main() {
    int max_limit = 100;
    vector<bool> isPrime_100 = sieveEratosthenes(max_limit);

    cout << "Kiem tra tinh nguyen to trong pham vi [" << 0 << ", " << max_limit << "]:\n";
    cout << "So 2: " << (isPrimeUsingSieve(2, max_limit, isPrime_100) ? "Nguyen to" : "Khong nguyen to") << "\n"; // true
    cout << "So 10: " << (isPrimeUsingSieve(10, max_limit, isPrime_100) ? "Nguyen to" : "Khong nguyen to") << "\n"; // false
    cout << "So 17: " << (isPrimeUsingSieve(17, max_limit, isPrime_100) ? "Nguyen to" : "Khong nguyen to") << "\n"; // true
    cout << "So 99: " << (isPrimeUsingSieve(99, max_limit, isPrime_100) ? "Nguyen to" : "Khong nguyen to") << "\n"; // false
    cout << "So 101: " << (isPrimeUsingSieve(101, max_limit, isPrime_100) ? "Nguyen to" : "Khong nguyen to") << "\n"; // Error message + false

    return 0;
}
*/

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>

// (Giả định hàm sieveEratosthenes từ ví dụ trước đã tồn tại hoặc được gọi)
// vector<bool> isPrime_global = sieveEratosthenes(MAX_LIMIT);

// Hàm liệt kê các số nguyên tố sử dụng kết quả sàng
void listPrimesUsingSieve(int max_limit, const vector<bool>& isPrime_sieved) {
    cout << "Cac so nguyen to trong pham vi [2, " << max_limit << "]:\n";
    // Duyệt từ 2 đến giới hạn tối đa
    for (int i = 2; i <= max_limit; ++i) {
        // Nếu isPrime_sieved[i] la true, thi i la so nguyen to
        if (isPrime_sieved[i]) {
            cout << i << " ";
        }
    }
    cout << "\n";
}

/*
int main() {
    int max_limit = 50;
    vector<bool> isPrime_50 = sieveEratosthenes(max_limit);

    listPrimesUsingSieve(max_limit, isPrime_50); // Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

    return 0;
}
*/

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>

// (Giả định hàm sieveEratosthenes từ ví dụ trước đã tồn tại hoặc được gọi)
// vector<bool> isPrime_global = sieveEratosthenes(MAX_LIMIT);

// Hàm đếm số lượng số nguyên tố trong phạm vi [2, limit]
int countPrimesUsingSieve(int limit, const vector<bool>& isPrime_sieved) {
    // Đảm bảo giới hạn đếm không vượt quá giới hạn đã sàng
    int actual_limit = min(limit, (int)isPrime_sieved.size() - 1);
    if (limit < 2) return 0; // Không có số nguyên tố nào <= 1

    int count = 0;
    // Duyệt từ 2 đến giới hạn cần đếm
    for (int i = 2; i <= actual_limit; ++i) {
        if (isPrime_sieved[i]) {
            count++;
        }
    }
    return count;
}

/*
int main() {
    int max_limit_sieve = 100;
    vector<bool> isPrime_100 = sieveEratosthenes(max_limit_sieve);

    int count_to_50 = countPrimesUsingSieve(50, isPrime_100); // Đếm đến 50
    cout << "So luong so nguyen to den 50: " << count_to_50 << "\n"; // Output: 15

    int count_to_100 = countPrimesUsingSieve(100, isPrime_100); // Đếm đến 100
     cout << "So luong so nguyen to den 100: " << count_to_100 << "\n"; // Output: 25

    return 0;
}
*/

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.