Bài 17.4: Bài tập thực hành sàng số nguyên tố trong C++

Chào mừng trở lại với chuỗi bài học C++! Hôm nay, chúng ta sẽ cùng nhau khám phá và thực hành một trong những thuật toán kinh điển nhất trong lĩnh vực tìm kiếm số nguyên tố: Thuật toán Sàng Eratosthenes (Sieve of Eratosthenes). Đây không chỉ là một kỹ thuật quan trọng trong lý thuyết số mà còn là một vũ khí cực kỳ mạnh mẽ và hiệu quả khi bạn cần tìm nhiều số nguyên tố trong một phạm vi nhất định, đặc biệt hữu ích trong các bài toán lập trình thi đấu.

Trước khi đi sâu vào "chiếc sàng" kỳ diệu này, hãy nhớ lại số nguyên tố là gì: là số tự nhiên lớn hơn 1 và chỉ có hai ước số dương phân biệt là 1 và chính nó. Việc kiểm tra tính nguyên tố của một số riêng lẻ (ví dụ: dùng vòng lặp chia thử từ 2 đến căn bậc hai của nó) khá đơn giản. Tuy nhiên, khi bạn cần tìm tất cả số nguyên tố dưới một con số N lớn, phương pháp kiểm tra từng số một trở nên kém hiệu quả một cách đáng kể. Đây chính là lúc Sàng Eratosthenes tỏa sáng!

Sàng Eratosthenes Hoạt Động Như Thế Nào?

Ý tưởng cốt lõi của Sàng Eratosthenes rất đơn giản nhưng thiên tài: thay vì kiểm tra từng số xem nó có phải là nguyên tố hay không, chúng ta sẽ bắt đầu từ các số nguyên tố đã biết và loại bỏ (đánh dấu là không nguyên tố) tất cả các bội số của chúng. Những số còn lại chưa bị loại bỏ chính là các số nguyên tố.

Hãy hình dung chúng ta muốn tìm tất cả số nguyên tố nhỏ hơn hoặc bằng N. Thuật toán tiến hành như sau:

  1. Tạo một danh sách (hoặc mảng) các số tự nhiên từ 0 đến N. Ban đầu, giả định tất cả các số (trừ 0 và 1) đều là số nguyên tố. Chúng ta có thể sử dụng một mảng boolean isPrime có kích thước N+1, khởi tạo tất cả các giá trị là true. Đánh dấu isPrime[0] và isPrime[1] là false.
  2. Bắt đầu với số nguyên tố đầu tiên, số 2.
  3. Lặp qua tất cả các bội số của 2 (lớn hơn 2) và đánh dấu chúng là không nguyên tố (false). Tức là đánh dấu 4, 6, 8, 10, ... là false.
  4. Tìm số tiếp theo trong danh sách mà vẫn còn được đánh dấu là true. Số này chắc chắn là số nguyên tố (vì nó không phải là bội số của bất kỳ số nguyên tố nhỏ hơn nào). Số tiếp theo sau 2 mà còn true là số 3.
  5. Lặp qua tất cả các bội số của 3 (lớn hơn 3) và đánh dấu chúng là không nguyên tố. Tức là đánh dấu 6, 9, 12, 15, ... là false. Lưu ý rằng một số (như 6) có thể đã bị đánh dấu rồi, điều này không sao cả.
  6. Tiếp tục quá trình này: tìm số tiếp theo còn true, đó là số nguyên tố mới, sau đó đánh dấu tất cả bội số của nó là false.
  7. Chúng ta chỉ cần thực hiện bước 6 cho đến khi số nguyên tố hiện tại p đạt đến căn bậc hai của N (tức là p * p <= N). Tại sao chỉ cần đến căn bậc hai của N? Bởi vì nếu một số k là hợp số (không nguyên tố), thì nó có thể được viết dưới dạng k = a * b, trong đó a <= sqrt(k) và b >= sqrt(k) (hoặc ngược lại). Nếu a > sqrt(k), thì b phải nhỏ hơn sqrt(k). Điều này có nghĩa là mọi hợp số k luôn có ít nhất một thừa số nguyên tố nhỏ hơn hoặc bằng căn bậc hai của nó. Nếu chúng ta đã loại bỏ tất cả các bội số của các số nguyên tố đến sqrt(N), thì bất kỳ số nào còn lại chưa bị đánh dấu false chắc chắn phải là nguyên tố.

Cài Đặt Sàng Eratosthenes trong C++

Chúng ta sẽ sử dụng vector<bool> để lưu trữ trạng thái nguyên tố của các số. Đây là một cấu trúc dữ liệu rất phù hợp cho bài toán này vì nó được tối ưu hóa bộ nhớ cho các giá trị boolean.

Đầu tiên, hãy xem xét một ví dụ cơ bản để tìm tất cả số nguyên tố nhỏ hơn hoặc bằng 30.

#include <iostream>
#include <vector>
#include <cmath> // Để dùng sqrt

int main() {
    int n = 30; // Giới hạn tìm kiếm

    // 1. Tạo vector boolean, mặc định coi tất cả là nguyên tố
    // Kích thước n+1 để bao gồm cả n
    vector<bool> isPrime(n + 1, true);

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

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

    // 4. In ra các số nguyên tố
    cout << "So nguyen to nho hon hoac bang " << n << " la:\n";
    for (int p = 2; p <= n; ++p) {
        if (isPrime[p] == true)
            cout << p << " ";
    }
    cout << endl;

    return 0;
}

Giải thích code:

  • Chúng ta khai báo vector<bool> isPrime(n + 1, true);. Điều này tạo ra một vector có kích thước n + 1, tất cả các phần tử ban đầu đều là true. isPrime[i] sẽ là true nếu i được coi là nguyên tố, và false nếu không.
  • isPrime[0] = isPrime[1] = false; xử lý trường hợp đặc biệt của 0 và 1.
  • Vòng lặp ngoài for (int p = 2; p * p <= n; ++p) duyệt qua các số từ 2 lên đến căn bậc hai của n. p đại diện cho số nguyên tố tiềm năng hiện tại.
  • if (isPrime[p] == true) kiểm tra xem p có còn được đánh dấu là nguyên tố hay không. Nếu có, điều đó xác nhận p là một số nguyên tố (vì nó chưa bị đánh dấu bởi các số nguyên tố nhỏ hơn).
  • Vòng lặp trong for (int i = p * p; i <= n; i += p) bắt đầu từ p*p (như đã giải thích ở trên để tối ưu) và duyệt qua tất cả các bội số của p trong phạm vi từ p*p đến n, đánh dấu chúng là false.
  • Cuối cùng, chúng ta lặp lại từ 2 đến n và in ra tất cả các chỉ số p mà isPrime[p] vẫn là true.

Kết quả của đoạn code trên sẽ là: So nguyen to nho hon hoac bang 30 la: 2 3 5 7 11 13 17 19 23 29

Khá ấn tượng phải không? Chỉ với vài vòng lặp, chúng ta đã tìm ra tất cả các số nguyên tố trong phạm vi này một cách rất hiệu quả.

Đóng Gói Thuật Toán Thành Hàm

Để dễ dàng tái sử dụng, chúng ta có thể đóng gói logic sàng này vào một hàm. Hàm có thể trả về vector isPrime hoặc thậm chí là một vector chứa trực tiếp các số nguyên tố tìm được.

Ví dụ, hàm trả về vector<bool>:

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

// Hàm thực hiện sàng Eratosthenes, trả về vector boolean
// isPrime[i] true nếu i là số nguyên tố
vector<bool> sieveOfEratosthenes(int n) {
    vector<bool> isPrime(n + 1, true);
    isPrime[0] = isPrime[1] = false;

    for (int p = 2; p * p <= n; ++p) {
        if (isPrime[p] == true) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }
    return isPrime;
}

int main() {
    int n = 100; // Tìm số nguyên tố đến 100

    // Gọi hàm sàng
    vector<bool> primes_status = sieveOfEratosthenes(n);

    // In ra các số nguyên tố dựa trên kết quả sàng
    cout << "So nguyen to nho hon hoac bang " << n << " la:\n";
    for (int p = 2; p <= n; ++p) {
        if (primes_status[p] == true) {
            cout << p << " ";
        }
    }
    cout << endl;

    // Ví dụ sử dụng kết quả để kiểm tra nhanh
    int num_to_check = 41;
    if (num_to_check >= 0 && num_to_check <= n) {
        if (primes_status[num_to_check]) {
            cout << num_to_check << " la so nguyen to." << endl;
        } else {
             cout << num_to_check << " khong phai la so nguyen to." << endl;
        }
    } else {
         cout << "So " << num_to_check << " vuot qua gioi han " << n << "." << endl;
    }

     num_to_check = 49;
     if (num_to_check >= 0 && num_to_check <= n) {
        if (primes_status[num_to_check]) {
            cout << num_to_check << " la so nguyen to." << endl;
        } else {
             cout << num_to_check << " khong phai la so nguyen to." << endl;
        }
    } else {
         cout << "So " << num_to_check << " vuot qua gioi han " << n << "." << endl;
    }


    return 0;
}

Giải thích code:

  • Hàm sieveOfEratosthenes(int n) nhận giới hạn n và trả về vector isPrime sau khi đã thực hiện sàng.
  • Trong main, chúng ta gọi hàm này để nhận về vector trạng thái nguyên tố.
  • Sau khi có primes_status, việc in ra các số nguyên tố hoặc kiểm tra tính nguyên tố của một số bất kỳ trong phạm vi 0 đến n trở nên cực kỳ nhanh chóng (độ phức tạp O(1) cho mỗi lần kiểm tra) vì chúng ta chỉ cần truy cập trực tiếp vào phần tử tại chỉ số tương ứng.

Ví dụ, kiểm tra 41 và 49 chỉ mất 2 thao tác truy cập mảng sau khi sàng.

Độ Phức Tạp Của Thuật Toán

Sàng Eratosthenes có độ phức tạp thời gian là O(N log log N). Nghe có vẻ phức tạp, nhưng thực tế nó gần như tuyến tính so với N. So với việc kiểm tra nguyên tố cho từng số một (độ phức tạp khoảng O(N sqrt(N)) cho N số), Sàng Eratosthenes vượt trội* hơn hẳn khi N đủ lớn.

Độ phức tạp không gian của thuật toán là O(N), vì chúng ta cần một mảng có kích thước N+1 để lưu trữ trạng thái của mỗi số.

Tại Sao Sàng Eratosthenes Lại Quan Trọng?

  • Hiệu quả: Đây là một trong những cách nhanh nhất để tạo danh sách các số nguyên tố dưới một giới hạn cho trước.
  • Ứng dụng: Được sử dụng rộng rãi trong lý thuyết số, mật mã học cơ bản, và đặc biệt là trong các bài toán lập trình thi đấu khi cần xử lý nhiều truy vấn liên quan đến số nguyên tố trong một phạm vi cố định.
  • Nền tảng: Hiểu Sàng Eratosthenes là nền tảng để học các thuật toán sàng nâng cao hơn hoặc các bài toán dựa trên tính chất của số nguyên tố.

Thực Hành Thêm!

Để nắm vững thuật toán này, bạn có thể thử các bài tập sau:

  1. Đếm số nguyên tố: Sửa đổi hàm sieveOfEratosthenes để nó trả về số lượng các số nguyên tố nhỏ hơn hoặc bằng n, thay vì vector boolean.
  2. Liệt kê trong khoảng: Sử dụng kết quả của sàng để in ra tất cả các số nguyên tố trong một khoảng [a, b] cho trước (với a >= 2).
  3. Tổng các số nguyên tố: Tính tổng của tất cả các số nguyên tố nhỏ hơn hoặc bằng n.
  4. Sàng và kiểm tra: Viết một chương trình sử dụng sàng để tạo danh sách nguyên tố đến 1 triệu, sau đó cho phép người dùng nhập vào các số và kiểm tra nhanh xem số đó có phải nguyên tố không.

Comments

There are no comments at the moment.