Số nguyên tố là một trong những khái niệm cơ bản nhất của số học, đồng thời cũng xuất hiện rất thường xuyên trong các bài toán lập trình thi đấu. Nhiều bài toán về ước số, phân tích thừa số nguyên tố, ước chung lớn nhất hay các kỹ thuật số học nâng cao đều bắt đầu từ việc hiểu số nguyên tố và biết cách xác định chúng một cách hiệu quả.

Trong bài viết này, chúng ta sẽ không bắt đầu ngay bằng một công thức hay một đoạn code đã được tối ưu sẵn. Thay vào đó, chúng ta sẽ đi từ cách suy nghĩ tự nhiên nhất: dựa trực tiếp vào định nghĩa để kiểm tra một số có phải số nguyên tố hay không. Sau đó, chúng ta sẽ quan sát những công việc không cần thiết trong cách làm ban đầu, tìm ra một nhận xét quan trọng về các cặp ước và từ đó giảm số phép kiểm tra xuống chỉ còn khoảng √n. Cuối cùng, khi bài toán yêu cầu tìm hoặc kiểm tra rất nhiều số nguyên tố cùng lúc, chúng ta sẽ tiếp tục thay đổi cách tiếp cận để xây dựng Sàng Eratosthenes.

1. Số nguyên tố là gì?

Một số nguyên dương n được gọi là số nguyên tố nếu n > 1 và n chỉ có đúng hai ước dương là 1 và chính nó. Ví dụ, số 5 là số nguyên tố vì các ước dương của 5 chỉ có 1 và 5. Tương tự, 7 cũng là số nguyên tố vì không tồn tại số nguyên nào trong khoảng từ 2 đến 6 có thể chia hết 7. Ngược lại, số 6 không phải là số nguyên tố vì ngoài 1 và 6, nó còn chia hết cho 2 và 3. Những số lớn hơn 1 nhưng không phải số nguyên tố thường được gọi là hợp số.

Một vài số nguyên tố đầu tiên là:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Có một trường hợp đặc biệt rất dễ gây nhầm lẫn: số 1 không phải là số nguyên tố. Theo định nghĩa, một số nguyên tố phải có đúng hai ước dương khác nhau, trong khi 1 chỉ có duy nhất một ước là chính nó. Vì vậy, khi cài đặt hàm kiểm tra số nguyên tố, chúng ta luôn phải xử lý riêng các số nhỏ hơn 2.

2. Bắt đầu từ cách suy nghĩ đơn giản nhất

Giả sử chúng ta được cho một số nguyên n và cần trả lời câu hỏi: n có phải là số nguyên tố hay không? Nếu chỉ dựa vào định nghĩa, cách suy nghĩ tự nhiên nhất là kiểm tra xem n có tồn tại một ước nào khác 1 và n hay không. Nếu tìm được ít nhất một số i thỏa mãn 2 ≤ i < n và n % i == 0, chúng ta có thể khẳng định ngay rằng n không phải số nguyên tố. Ngược lại, nếu đã thử tất cả các số từ 2 đến n - 1 mà không tìm thấy số nào chia hết n, điều đó có nghĩa rằng n không có ước nào ngoài 1 và chính nó. Khi đó, n là số nguyên tố.

Ví dụ với n = 7

Ta lần lượt kiểm tra:

7 % 2 != 0
7 % 3 != 0
7 % 4 != 0
7 % 5 != 0
7 % 6 != 0

Không có số nào trong khoảng từ 2 đến 6 chia hết 7, vì vậy 7 là số nguyên tố.

Nếu thay 7 bằng 12, tình huống sẽ khác. Ngay khi thử i = 2, ta có:

12 % 2 == 0

Chỉ cần tìm thấy một ước như vậy là đủ để kết luận 12 không phải số nguyên tố. Chúng ta không cần tiếp tục thử 3, 4, 5,... nữa. Từ suy nghĩ trên, ta có thể viết một hàm kiểm tra như sau:

bool isPrime(long long n) {
    if (n < 2) return false;

    for (long long i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

Đây là một thuật toán hoàn toàn đúng và cũng rất dễ hiểu. Tuy nhiên, vấn đề nằm ở số lượng phép kiểm tra mà nó phải thực hiện.

3. Vì sao cách làm trên quá chậm?

Giả sử n là một số nguyên tố lớn. Vì số nguyên tố không chia hết cho bất kỳ số nào từ 2 đến n - 1, vòng lặp sẽ phải chạy gần như toàn bộ khoảng này trước khi có thể trả về true. Do đó, số lần kiểm tra trong trường hợp xấu nhất tỷ lệ với n, và độ phức tạp của thuật toán là: O(n)

Nếu n = 1000, việc kiểm tra vài trăm số vẫn chưa phải vấn đề lớn. Nhưng nếu n có giá trị khoảng 10^9, cách làm này có thể phải thực hiện gần một tỷ phép chia dư. Trong một bài toán lập trình thi đấu, số lượng phép tính như vậy gần như chắc chắn sẽ dẫn đến quá thời gian. Vì vậy, trước khi nghĩ đến việc viết một thuật toán hoàn toàn mới, chúng ta nên đặt một câu hỏi đơn giản hơn: Có thật sự cần kiểm tra mọi số từ 2 đến n - 1 hay không? Để trả lời câu hỏi này, hãy quan sát kỹ hơn cách các ước của một số xuất hiện.

4. Các ước luôn xuất hiện theo cặp

Giả sử n là một hợp số. Khi đó, theo định nghĩa, tồn tại hai số nguyên a và b, đều lớn hơn 1, sao cho:

n = a × b

Điều này có nghĩa rằng các ước của n thường xuất hiện thành từng cặp. Nếu a là một ước của n, thì số b = n / a cũng là một ước của n.

Hãy xét số 36. Ta có thể viết 36 dưới nhiều dạng tích khác nhau:

36 = 1 × 36
36 = 2 × 18
36 = 3 × 12
36 = 4 × 9
36 = 6 × 6

Nếu tiếp tục đổi thứ tự hai thừa số, chúng ta sẽ có:

36 = 9 × 4
36 = 12 × 3
36 = 18 × 2
36 = 36 × 1

Có thể biểu diễn các cặp ước này bằng bảng:

Điều đáng chú ý là các cặp bắt đầu lặp lại sau khi chúng ta đi qua 6, mà: √36 = 6. Trước √36, chúng ta gặp những ước nhỏ như 2, 3, 4. Sau √36, các ước 9, 12, 18 thực chất chỉ là những số đã được ghép cặp tương ứng với 4, 3, 2.

Nói cách khác, khi đã biết:

36 = 3 × 12

thì việc sau đó phát hiện:

36 = 12 × 3

không mang lại thêm thông tin mới. Đây là dấu hiệu cho thấy chúng ta không cần kiểm tra các ước quá lớn.

5. Vì sao chỉ cần kiểm tra đến √n?

Nhận xét ở ví dụ trên không chỉ đúng với 36, mà đúng với mọi số nguyên dương. Giả sử n là hợp số. Khi đó tồn tại: n = a × b ới a > 1 và b > 1. Bây giờ hãy giả sử ngược lại rằng cả hai số a và b đều lớn hơn √n. Khi đó:

a > √n
b > √n

Nếu nhân hai bất đẳng thức này lại với nhau, ta nhận được:

a × b > √n × √n

mà:

√n × √n = n

nên:

a × b > n

Tuy nhiên ngay từ đầu chúng ta đã có a × b = n. Hai kết luận này mâu thuẫn với nhau. Vì vậy, giả sử rằng cả a và b đều lớn hơn √n là không thể xảy ra. Trong bất kỳ cặp ước nào a × b = n, luôn phải tồn tại ít nhất một trong hai số không lớn hơn √n. Đây là nhận xét quan trọng nhất của thuật toán: Nếu n là hợp số, chắc chắn n có ít nhất một ước nằm trong đoạn từ 2 đến √n.

Từ đó, ta có thể suy luận theo chiều ngược lại. Nếu đã thử tất cả các số từ 2 đến √n nhưng không tìm thấy số nào chia hết n, thì không thể tồn tại một cặp ước nào khác. Do đó n phải là số nguyên tố. Nhờ nhận xét này, chúng ta có thể loại bỏ phần lớn những phép kiểm tra không cần thiết của thuật toán ban đầu.

6. Kiểm tra số nguyên tố trong O(√n)

Thay vì chạy vòng lặp từ 2 đến n - 1, chúng ta chỉ cần chạy đến √n. Một cách cài đặt trực tiếp có thể sử dụng sqrt(n), nhưng trong C++ người ta thường viết điều kiện:

i * i <= n

Điều kiện này tương đương với:

i <= √n

Hàm kiểm tra trở thành:

bool isPrime(long long n) {
    if (n < 2) return false;

    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

Ví dụ: kiểm tra n = 37

Ta có:

√37 ≈ 6.08

Vì vậy, chúng ta chỉ cần thử các số nguyên:

2, 3, 4, 5, 6

Không số nào chia hết 37, nên 37 là số nguyên tố. Điều đáng chú ý là thuật toán hoàn toàn không cần kiểm tra các số từ 7 đến 36. Nếu 37 có một ước lớn hơn √37, ước đó bắt buộc phải đi kèm với một ước nhỏ hơn √37. Vì chúng ta đã kiểm tra toàn bộ các ước nhỏ mà không tìm thấy gì, nên một ước lớn như vậy cũng không thể tồn tại.

Ví dụ: kiểm tra n = 91

Ta có:

√91 ≈ 9.54

Vì vậy chỉ cần thử các số từ 2 đến 9. Khi đến 7:

91 % 7 == 0

Ta kết luận ngay 91 là hợp số, vì:

91 = 7 × 13

Ở đây 13 lớn hơn √91, nhưng điều đó không quan trọng. Cặp ước của nó là 7, và 7 nằm phía nhỏ hơn √91, nên thuật toán vẫn tìm được. Đây chính là lý do việc kiểm tra đến √n là đầy đủ chứ không chỉ là một mẹo giúp chương trình chạy nhanh hơn.

7. Độ phức tạp đã được cải thiện như thế nào?

Thuật toán đầu tiên có thể phải thử gần n giá trị, nên có độ phức tạp O(n). Sau khi sử dụng nhận xét về cặp ước, chúng ta chỉ cần kiểm tra khoảng √n giá trị. Vì vậy độ phức tạp giảm xuống còn:

O(√n)

Sự khác biệt này rất lớn khi n tăng.

Ví dụ với:

n = 1 000 000 000

thuật toán O(n) về lý thuyết có thể phải thực hiện gần một tỷ lần kiểm tra. Trong khi đó:

√1 000 000 000 ≈ 31623

Thuật toán O(√n) chỉ cần khoảng vài chục nghìn phép thử. Đây là một mức cải thiện rất đáng kể.

8. Có thể giảm thêm một nửa số lần kiểm tra

Chúng ta còn có một nhận xét đơn giản khác: Mọi số chẵn lớn hơn 2 đều không phải số nguyên tố. Lý do rất rõ ràng. Nếu một số chẵn lớn hơn 2, nó luôn chia hết cho 2, vì vậy ngoài 1 và chính nó, nó còn có thêm một ước nữa là 2. Do đó, ta có thể xử lý riêng số 2. Sau đó, nếu n là số chẵn thì trả về false ngay. Khi đã biết n là số lẻ, không cần thử các ước chẵn nữa vì một số lẻ không thể chia hết cho một số chẵn.

Ta chỉ cần kiểm tra:

3, 5, 7, 9, 11, ...

đến √n.

bool isPrime(long long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

Về mặt độ phức tạp, thuật toán vẫn là O(√n), bởi vì chúng ta chỉ giảm số phép kiểm tra đi một hằng số. Tuy nhiên, trong thực tế chương trình sẽ nhanh hơn do chỉ phải thử khoảng một nửa số lượng ứng viên. Với các bài toán yêu cầu kiểm tra một hoặc một vài số có phải số nguyên tố hay không, thuật toán O(√n) thường đã là lựa chọn rất phù hợp.

9. Nhưng chuyện gì xảy ra khi cần kiểm tra rất nhiều số?

Hãy xét một bài toán khác: Hãy tìm tất cả các số nguyên tố không vượt quá 1 000 000.

Một cách dễ nghĩ là chạy:

isPrime(2);
isPrime(3);
isPrime(4);
...
isPrime(1000000);

Về mặt logic, cách này hoàn toàn đúng. Tuy nhiên, chúng ta đang kiểm tra từng số một cách độc lập, dẫn đến rất nhiều công việc bị lặp lại. Ví dụ, khi kiểm tra 100, chúng ta thử xem nó có chia hết cho 2 hay không. Khi kiểm tra 102, ta lại tiếp tục thử chia cho 2. Đối với 104, 106, 108,... công việc tương tự tiếp tục được lặp lại. Trong khi đó, chỉ cần biết 2 là số nguyên tố, chúng ta có thể khẳng định ngay rằng:

4, 6, 8, 10, 12, 14, ...

đều không phải số nguyên tố, bởi vì tất cả chúng đều chia hết cho 2. Tương tự, khi biết 3 là số nguyên tố, chúng ta có thể loại:

6, 9, 12, 15, 18, 21, ...

Thay vì kiểm tra từng số xem nó có ước hay không, chúng ta có thể dùng các số nguyên tố đã biết để loại hàng loạt những số chắc chắn không phải nguyên tố. Sự thay đổi cách đặt câu hỏi này chính là ý tưởng dẫn đến Sàng Eratosthenes.

10. Ý tưởng của Sàng Eratosthenes

Sàng Eratosthenes được sử dụng để tìm tất cả các số nguyên tố từ 1 đến một giới hạn n. Ta tạo một mảng: isPrime[i] Trong đó isPrime[i] cho biết số i hiện có được xem là số nguyên tố hay không. Ban đầu, chúng ta chưa biết số nào là hợp số, vì vậy tạm thời xem tất cả các số từ 2 đến n là số nguyên tố: vector<bool> isPrime(n + 1, true);

Riêng 0 và 1 chắc chắn không phải số nguyên tố:

isPrime[0] = false;
isPrime[1] = false;

Sau đó chúng ta duyệt các số từ nhỏ đến lớn. Khi gặp một số p vẫn chưa bị loại, điều đó có nghĩa rằng không có số nhỏ hơn nào chia hết p. Vì vậy p phải là số nguyên tố. Khi đã biết p là số nguyên tố, mọi bội của p lớn hơn p đều chắc chắn là hợp số. Chúng ta sẽ đánh dấu tất cả các bội đó thành false.

11. Mô phỏng Sàng Eratosthenes với n = 30

Ban đầu, các số từ 2 đến 30 đều đang được xem là ứng viên nguyên tố:

2  3  4  5  6  7  8  9  10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

Xử lý số 2

Số 2 chưa bị đánh dấu là hợp số. Vì nó là số nhỏ nhất đang còn lại, 2 chắc chắn là số nguyên tố.

Mọi bội của 2 lớn hơn 2 đều là hợp số:

4, 6, 8, 10, 12, 14, 16, 18, 20, ...

Ta đánh dấu toàn bộ những số này là không nguyên tố.

Sau bước này, các số chẵn lớn hơn 2 đã bị loại.

Xử lý số 3

Số 3 vẫn chưa bị loại, nên 3 là số nguyên tố.

Mọi bội của 3 lớn hơn 3 đều là hợp số:

6, 9, 12, 15, 18, 21, 24, 27, 30

Một vài số như 6, 12, 18 đã bị loại khi xử lý số 2. Việc đánh dấu chúng thêm một lần không làm thuật toán sai, nhưng rõ ràng đó là công việc lặp lại.

Chúng ta sẽ sớm tìm cách tránh phần công việc thừa này.

Đến số 4

Số 4 đã bị đánh dấu là hợp số khi xử lý 2, vì:

4 = 2 × 2

Do đó chúng ta không sử dụng 4 để tiếp tục loại các số khác.

Điều này rất quan trọng: trong quá trình sàng, chúng ta chỉ xử lý những số chưa bị loại. Những số đó chính là các số nguyên tố.

Đến số 5

Số 5 chưa bị loại, nên 5 là số nguyên tố. Về lý thuyết, ta có thể bắt đầu loại:

10, 15, 20, 25, 30, ...

Tuy nhiên, 10 và 20 đã bị loại bởi 2, còn 15 và 30 đã bị loại bởi 3.

Chỉ có 25 là số đầu tiên mà chúng ta thực sự cần xử lý ở bước của 5.

Từ đây xuất hiện một tối ưu rất quan trọng khác.

12. Vì sao có thể bắt đầu đánh dấu từ p²?

Giả sử chúng ta đang xử lý một số nguyên tố p.

Các bội của p lần lượt là:

2p, 3p, 4p, 5p, ..., p × p, ...

Hãy xét các bội đứng trước p². Chúng có dạng:

k × p

với:

2 ≤ k < p

Nhưng vì k < p, số k đã được xét trước p. Do đó, số k × p chắc chắn đã bị đánh dấu từ một bước trước đó.

Ví dụ khi xử lý p = 5, các bội nhỏ hơn 25 là:

10 = 2 × 5
15 = 3 × 5
20 = 4 × 5

10 đã bị đánh dấu khi xử lý 2. 15 đã bị đánh dấu khi xử lý 3. 20 cũng đã bị đánh dấu khi xử lý 2.

Vì vậy, khi đến 5, không có lý do gì để bắt đầu lại từ 10. Chúng ta có thể bỏ qua toàn bộ phần này và bắt đầu trực tiếp từ:

5² = 25

Tổng quát hơn, khi xử lý một số nguyên tố p, ta bắt đầu đánh dấu từ:

p × p

rồi tăng dần mỗi lần p đơn vị:

p², p² + p, p² + 2p, p² + 3p, ...

Đây chính là vòng lặp thường thấy trong cài đặt Sàng Eratosthenes:

for (long long multiple = p * p;
     multiple <= n;
     multiple += p) {
    isPrime[multiple] = false;
}

13. Vì sao vòng lặp ngoài chỉ cần chạy đến √n?

Trong cài đặt chuẩn của Sàng Eratosthenes, vòng lặp ngoài thường có dạng:

for (long long p = 2; p * p <= n; p++)

Có thể bạn sẽ thắc mắc: nếu chúng ta cần tìm số nguyên tố đến n, tại sao vòng lặp xử lý lại dừng ở √n?

Lý do thực chất giống với nhận xét chúng ta đã sử dụng khi kiểm tra một số nguyên tố.

Giả sử có một hợp số x ≤ n. Vì x là hợp số, ta có thể viết:

x = a × b

với a > 1 và b > 1.

Trong hai số a và b, ít nhất một số không lớn hơn √x. Vì x ≤ n, ta cũng có:

√x ≤ √n

Do đó, mọi hợp số không vượt quá n đều có ít nhất một ước không vượt quá √n.

Khi chúng ta đã xử lý toàn bộ các số nguyên tố p ≤ √n, mỗi hợp số trong đoạn từ 2 đến n chắc chắn đã bị một trong những p đó đánh dấu.

Vì vậy, sau khi vòng lặp vượt qua √n, không còn hợp số nào mới cần được loại nữa. Những số chưa bị đánh dấu đến lúc này chắc chắn là số nguyên tố.

14. Cài đặt hoàn chỉnh

Sau tất cả các nhận xét trên, ta có cài đặt Sàng Eratosthenes như sau:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<bool> isPrime(n + 1, true);

    if (n >= 0) isPrime[0] = false;
    if (n >= 1) isPrime[1] = false;

    for (long long p = 2; p * p <= n; p++) {
        if (!isPrime[p]) {
            continue;
        }

        for (long long multiple = p * p;
             multiple <= n;
             multiple += p) {
            isPrime[multiple] = false;
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << ' ';
        }
    }
}

Nếu nhập:

30

chương trình sẽ in:

2 3 5 7 11 13 17 19 23 29

Đó chính là toàn bộ các số nguyên tố không vượt quá 30.

15. Độ phức tạp của Sàng Eratosthenes

Sàng Eratosthenes có độ phức tạp thời gian:

O(n log log n)

và sử dụng:

O(n)

bộ nhớ để lưu trạng thái của các số từ 0 đến n.

O(n log log n) có thể trông hơi lạ nếu bạn mới học độ phức tạp. Ở giai đoạn này, điều quan trọng hơn là hiểu rằng nó gần tuyến tính và rất nhanh trong thực tế.

So với việc gọi hàm kiểm tra O(√x) cho từng số x từ 1 đến n, Sàng Eratosthenes hiệu quả hơn rất nhiều khi cần xử lý cả một đoạn số liên tiếp.

Ví dụ, nếu bài toán có 100000 truy vấn và mỗi truy vấn hỏi:

x có phải số nguyên tố hay không?

với mọi x ≤ 10^6, chúng ta có thể sàng trước toàn bộ đoạn từ 1 đến 10^6. Sau đó, mỗi truy vấn chỉ cần kiểm tra:

isPrime[x]

Thao tác này có độ phức tạp O(1).

Như vậy, thay vì lặp lại quá trình tìm ước hàng trăm nghìn lần, chúng ta chỉ cần thực hiện một lần tiền xử lý và sử dụng kết quả cho tất cả các truy vấn sau đó.

16. Nên sử dụng cách nào?

Không có một thuật toán duy nhất phù hợp với mọi bài toán. Điều quan trọng là nhìn vào yêu cầu của đề để lựa chọn cách xử lý phù hợp.

Thuật toán ngây thơ không phải là một thuật toán “vô dụng”. Nó đóng vai trò rất quan trọng trong quá trình tư duy, bởi chính từ việc quan sát những công việc thừa của lời giải đơn giản, chúng ta mới tìm được hướng tối ưu.

Trong Competitive Programming, đây là một thói quen rất nên rèn luyện:

Trước tiên hãy tìm một lời giải đơn giản và đúng. Sau đó mới phân tích xem lời giải đang lãng phí thời gian ở đâu và liệu có tính chất nào giúp loại bỏ phần công việc không cần thiết hay không.

17. Một số lỗi thường gặp

Quên rằng 0 và 1 không phải số nguyên tố

Khi sử dụng Sàng Eratosthenes, chúng ta thường khởi tạo:

vector<bool> isPrime(n + 1, true);

Nếu dừng tại đây, isPrime[0] và isPrime[1] cũng đang có giá trị true, điều này là sai.

Vì vậy cần nhớ đặt:

isPrime[0] = false;
isPrime[1] = false;

nếu các chỉ số đó tồn tại.

Nghĩ rằng chỉ cần kiểm tra đến < √n

Khi kiểm tra một số nguyên tố, cần xét cả trường hợp i² = n.

Ví dụ:

n = 49

Ta có:

√49 = 7

và:

49 = 7 × 7

Nếu vòng lặp chỉ kiểm tra:

i * i < n

thì i = 7 sẽ không được xét và chương trình có thể kết luận sai rằng 49 là số nguyên tố.

Do đó điều kiện đúng là:

i * i <= n

Sàng từ 2 * p thay vì p * p

Đoạn code sau vẫn cho kết quả đúng:

for (int multiple = 2 * p;
     multiple <= n;
     multiple += p) {
    isPrime[multiple] = false;
}

Tuy nhiên, nhiều bội nhỏ hơn p² đã được xử lý bởi các số nhỏ hơn trước đó. Vì vậy bắt đầu từ p² giúp tránh một lượng đáng kể công việc lặp lại:

for (long long multiple = 1LL * p * p;
     multiple <= n;
     multiple += p) {
    isPrime[multiple] = false;
}

Cẩn thận với p * p

Nếu p được lưu bằng int và có giá trị lớn, phép nhân:

p * p

có thể vượt quá giới hạn của kiểu int trước khi được so sánh với n.

Một cách đơn giản để tránh vấn đề này là sử dụng long long hoặc ép phép nhân sang long long:

1LL * p * p

18. Nhìn lại quá trình tối ưu

• Điều quan trọng nhất trong bài này không phải là học thuộc ba đoạn code khác nhau. Điều đáng học hơn là cách chúng ta đi từ một lời giải rất đơn giản đến một lời giải tốt hơn thông qua các nhận xét. Ban đầu, dựa trực tiếp vào định nghĩa, chúng ta kiểm tra mọi số từ 2 đến n - 1. Đây là lời giải O(n).
• Sau đó, chúng ta nhận ra rằng các ước của một số xuất hiện theo cặp. Nếu: n = a × b thì ít nhất một trong hai số a, b phải không lớn hơn √n. Nhờ vậy, việc kiểm tra một số nguyên tố chỉ còn cần thực hiện đến √n, đưa độ phức tạp xuống O(√n).
• Tuy nhiên, khi cần xử lý hàng loạt số, ngay cả việc gọi thuật toán O(√n) nhiều lần vẫn khiến rất nhiều phép kiểm tra bị lặp lại. Khi đó, chúng ta tiếp tục thay đổi cách nhìn: thay vì lấy từng số và đi tìm ước của nó, ta lấy một số nguyên tố và loại toàn bộ các bội của số nguyên tố đó. Từ suy nghĩ ấy, chúng ta có Sàng Eratosthenes. Đây cũng là một trong những kiểu tư duy quan trọng nhất khi học thuật toán: không cố gắng đoán ngay lời giải tối ưu, mà bắt đầu từ một lời giải đúng, hiểu thật rõ nó, sau đó từng bước loại bỏ những công việc không cần thiết.

19. Bài tập luyện tập

Sau khi hiểu các ý tưởng trong bài, bạn có thể luyện tập theo thứ tự từ đơn giản đến nâng cao:

1. Kiểm tra một số n có phải số nguyên tố hay không.
2. Đếm có bao nhiêu số nguyên tố từ 1 đến n.
3. In toàn bộ các số nguyên tố không vượt quá n.
4. Cho Q truy vấn, mỗi truy vấn chứa một số x. Hãy xác định x có phải số nguyên tố hay không.
5. Tìm số nguyên tố lớn nhất không vượt quá n.
6. Đếm số nguyên tố nằm trong đoạn [L, R].
7. Tính tổng tất cả các số nguyên tố không vượt quá n.

Nếu vẫn chưa thực sự hiểu tại sao thuật toán O(√n) hoặc Sàng Eratosthenes đúng, hãy thử mô phỏng bằng tay với những số nhỏ như 30, 50 hoặc 100. Việc tự viết ra các cặp ước và tự đánh dấu các bội thường giúp hiểu bản chất của thuật toán tốt hơn nhiều so với việc chỉ học thuộc code.