Bài 17.1: Thuật toán sàng Eratosthenes trong C++

Chào mừng các bạn quay trở lại với chuỗi bài viết về C++ của FullhouseDev! Hôm nay, chúng ta sẽ đi sâu vào thế giới của các con số và khám phá một trong những thuật toán cổ điển nhất, nhưng vô cùng hiệu quả: Thuật toán sàng Eratosthenes (Sieve of Eratosthenes).

Bạn đã bao giờ cần tìm tất cả các số nguyên tố nhỏ hơn một số N nào đó chưa? Nếu N nhỏ, việc kiểm tra từng số có vẻ đơn giản. Nhưng khi N lớn, phương pháp "kiểm tra từng số" trở nên cực kỳ chậm. Đó là lúc chúng ta cần đến một công cụ mạnh mẽ hơn như Sàng Eratosthenes.

Số Nguyên Tố Là Gì? Nhắc Lại Kiến Thức Cũ

Trước khi đi vào thuật toán, hãy cùng nhắc lại định nghĩa cơ bản: Một số nguyên dương lớn hơn 1 được gọi là số nguyên tố nếu nó chỉ có hai ước dương phân biệt là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11, 13,... là các số nguyên tố. Các số 4 (ước: 1, 2, 4), 6 (ước: 1, 2, 3, 6), 9 (ước: 1, 3, 9),... không phải là số nguyên tố; chúng được gọi là hợp số. Đặc biệt, số 1 không phải là số nguyên tố cũng không phải hợp số.

Phương Pháp "Ngây Thơ" (Naive Approach)

Cách đơn giản nhất để kiểm tra một số n có phải là số nguyên tố không là thử chia n cho tất cả các số từ 2 đến sqrt(n). Nếu n chia hết cho bất kỳ số nào trong khoảng này, nó không phải số nguyên tố. Ngược lại, nó là số nguyên tố.

Để tìm tất cả số nguyên tố đến N bằng cách này, ta sẽ lặp qua tất cả các số từ 2 đến N và áp dụng phép kiểm tra trên cho từng số.

#include <iostream>
#include <cmath> // Đối với sqrt

// Hàm kiểm tra một số có phải là số nguyên tố không
bool isPrimeNaive(int n) {
    if (n <= 1) return false; // 0 và 1 không phải số nguyên tố
    for (int i = 2; i <= sqrt(n); ++i) {
        if (n % i == 0) {
            return false; // Tìm thấy ước số khác, không phải nguyên tố
        }
    }
    return true; // Không tìm thấy ước số, là nguyên tố
}

int main() {
    int limit = 30;
    cout << "So nguyen to den " << limit << " (phuong phap naive):" << endl;
    for (int i = 2; i <= limit; ++i) {
        if (isPrimeNaive(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

Giải thích ví dụ:

Chúng ta định nghĩa hàm isPrimeNaive để kiểm tra tính nguyên tố của từng số.
Trong main, chúng ta lặp từ 2 đến limit (ở đây là 30).
Với mỗi số i, chúng ta gọi isPrimeNaive(i).
Nếu hàm trả về true, chúng ta in số i.

Phương pháp này hoạt động đúng, nhưng nó không hiệu quả khi giới hạn N lớn. Độ phức tạp xấp xỉ O(N * sqrt(N)). Tưởng tượng N là 10^7, 10^8, bạn sẽ phải chờ rất lâu! Đây là lúc Sàng Eratosthenes tỏa sáng.

Thuật Toán Sàng Eratosthenes: Khử Bỏ Hợp Số

Thuật toán Sàng Eratosthenes, được đặt theo tên nhà toán học Hy Lạp cổ đại Eratosthenes, tiếp cận vấn đề theo hướng ngược lại. Thay vì kiểm tra từng số xem nó có phải nguyên tố không, thuật toán loại bỏ (hay đánh dấu) tất cả các hợp số một cách có hệ thống. Những số còn lại sau quá trình sàng lọc chính là các số nguyên tố.

Ý tưởng cốt lõi:

Bắt đầu với một danh sách tất cả các số nguyên dương từ 2 đến N, ban đầu coi tất cả đều là số nguyên tố tiềm năng.
Lấy số chưa được đánh dấu nhỏ nhất (ban đầu là 2). Số này chắc chắn là số nguyên tố.
Đánh dấu (loại bỏ) tất cả các bội số của số nguyên tố vừa tìm được (lớn hơn chính nó) là hợp số. Ví dụ với số 2, ta đánh dấu 4, 6, 8, 10,...
Chuyển sang số chưa được đánh dấu nhỏ nhất tiếp theo (sau khi xử lý 2, số chưa đánh dấu nhỏ nhất tiếp theo là 3). Số này là số nguyên tố.
Đánh dấu tất cả các bội số của 3 (lớn hơn 3) là hợp số: 6, 9, 12, 15,... (Lưu ý: 6 đã bị đánh dấu bởi 2, điều này không sao cả).
Lặp lại quá trình này cho đến khi xét đến số nguyên tố P mà P*P lớn hơn N. Tại sao lại là P*P? Vì mọi hợp số k nhỏ hơn hoặc bằng N đều có ít nhất một ước số nguyên tố p mà p <= sqrt(k). Do đó, nếu một số k là hợp số, nó sẽ bị đánh dấu bởi một số nguyên tố p <= sqrt(k) trong quá trình sàng lọc. Nếu k > sqrt(N), thì ước nguyên tố nhỏ nhất của nó p phải nhỏ hơn sqrt(k). Nếu p > sqrt(N), thì ước còn lại q = k/p phải nhỏ hơn sqrt(N), và k đã bị đánh dấu bởi q hoặc các ước của q rồi. Do đó, ta chỉ cần sàng lọc bằng các số nguyên tố đến sqrt(N).

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

Chúng ta có thể sử dụng một mảng boolean (hay vector<bool>) để theo dõi trạng thái của các số: true nghĩa là số đó chưa bị đánh dấu (tiềm năng là nguyên tố), false nghĩa là số đó đã bị đánh dấu (là hợp số).

#include <iostream>
#include <vector>
#include <cmath> // Đối với sqrt

// Hàm thực hiện thuật toán sàng Eratosthenes
vector<bool> sieveOfEratosthenes(int n) {
    // 1. Tạo một vector boolean 'isPrime' có kích thước n+1
    // Ban đầu coi tất cả các số từ 0 đến n là nguyên tố tiềm năng (đặt là true)
    vector<bool> isPrime(n + 1, true);

    // 2. 0 và 1 không phải là số nguyên tố, đánh dấu false
    isPrime[0] = isPrime[1] = false;

    // 3. Bắt đầu quá trình sàng lọc từ số 2
    // Chỉ cần lặp đế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, tức p chưa bị đánh dấu
        // => p là số nguyên tố
        if (isPrime[p] == true) {
            // 4. Đánh dấu tất cả các bội số của p (lớn hơn p*p) là false
            // Bắt đầu từ p*p vì các bội nhỏ hơn (p*2, p*3,...p*(p-1))
            // đã bị đánh dấu bởi các số nguyên tố nhỏ hơn p rồi.
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }

    // 5. isPrime[i] là true nghĩa là i là số nguyên tố
    return isPrime;
}

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

    // Thực hiện sàng Eratosthenes
    vector<bool> primesStatus = sieveOfEratosthenes(limit);

    // In ra các số nguyên tố tìm được
    cout << "Cac so nguyen to den " << limit << " (Sieve of Eratosthenes):" << endl;
    for (int i = 2; i <= limit; ++i) {
        if (primesStatus[i]) {
            cout << i << " ";
        }
    }
    cout << endl;

    // Ví dụ kiểm tra một số cụ thể (sử dụng kết quả sàng)
    int number_to_check = 97;
    if (number_to_check >= 0 && number_to_check <= limit) {
         if (primesStatus[number_to_check]) {
             cout << number_to_check << " la so nguyen to." << endl;
         } else {
             cout << number_to_check << " khong phai la so nguyen to." << endl;
         }
    } else {
        cout << "So can kiem tra (" << number_to_check << ") ngoai gioi han san." << endl;
    }

    return 0;
}

Giải thích Code:

vector<bool> isPrime(n + 1, true);: Chúng ta tạo một vector có kích thước n + 1. isPrime[i] sẽ lưu trữ trạng thái của số i. Ban đầu, mọi số từ 0 đến n đều được giả định là nguyên tố tiềm năng (true). vector<bool> là một kiểu dữ liệu đặc biệt trong C++ được tối ưu hóa về bộ nhớ để lưu trữ các giá trị boolean.
isPrime[0] = isPrime[1] = false;: Số 0 và 1 không phải là số nguyên tố, nên ta đánh dấu chúng là false.
for (int p = 2; p * p <= n; ++p): Vòng lặp ngoài này duyệt qua các số tiềm năng là nguyên tố, bắt đầu từ 2. Chúng ta chỉ cần lặp đến sqrt(n) (hoặc p*p <= n) vì lý do đã giải thích ở trên, giúp tối ưu đáng kể.
if (isPrime[p] == true): Nếu isPrime[p] vẫn là true, điều đó có nghĩa là p chưa bị đánh dấu bởi bất kỳ số nguyên tố nhỏ hơn nào trước đó. Do đó, p là một số nguyên tố thực sự.
for (int i = p * p; i <= n; i += p): Vòng lặp trong này thực hiện việc sàng. Nếu p là nguyên tố, chúng ta đánh dấu tất cả các bội số của p là hợp số. Chúng ta bắt đầu từ p * p vì các bội số nhỏ hơn (p * 2, p * 3,..., p * (p-1)) chắc chắn đã bị đánh dấu bởi các số nguyên tố nhỏ hơn p. Ví dụ, 4, 6, 8,... đã bị đánh dấu bởi 2; 9, 12, 15,... đã bị đánh dấu bởi 3 (hoặc 2). Việc bắt đầu từ p*p là một tối ưu quan trọng. Ta tăng i lên p sau mỗi lần lặp (i += p) để di chuyển qua các bội số của p.
return isPrime;: Hàm trả về vector isPrime, nơi isPrime[i] là true nếu i là số nguyên tố, và false nếu là hợp số (hoặc 0, 1).
Trong main: Chúng ta gọi hàm sieveOfEratosthenes để nhận về vector trạng thái. Sau đó, lặp từ 2 đến limit và in ra các chỉ số i mà primesStatus[i] là true. Chúng ta cũng thêm một ví dụ nhỏ về cách sử dụng kết quả sàng để kiểm tra nhanh một số cụ thể.

Hiệu Quả Của Sàng Eratosthenes

Độ phức tạp thời gian của Sàng Eratosthenes là xấp xỉ O(N log log N), vốn nhanh hơn rất nhiều so với O(N sqrt(N)) của phương pháp naive khi N lớn. Đây là lý do tại sao nó là thuật toán được lựa chọn để tìm số nguyên tố trong một phạm vi nhất định.

Độ phức tạp không gian là O(N), vì chúng ta cần một mảng có kích thước N để lưu trạng thái.

Comments

There are no comments at the moment.