Sàng Eratosthenes

Mức độ: Cơ bản

Bài Số nguyên tố kiểm tra một số rất nhanh. Nhưng khi đề hỏi về mọi số đến 10⁷ (đếm số nguyên tố, liệt kê, trả lời nhiều câu hỏi…), kiểm tra từng số sẽ quá chậm. Sàng Eratosthenes (mang tên một nhà toán học Hy Lạp cổ đại) tìm được mọi số nguyên tố đến 10⁷ chỉ với khoảng 3 × 10⁷ phép tính, thường chạy xong trong khoảng một giây hoặc nhanh hơn (tùy máy và ngôn ngữ).

Ý tưởng: gạch bỏ bội số

Viết các số từ 2 đến 30. Lặp lại:

Lấy số nhỏ nhất chưa bị gạch, đó là số nguyên tố.
Gạch bỏ mọi bội của nó (trừ chính nó), vì các bội đó đều là hợp số.

Bước	Số nguyên tố	Gạch bỏ
1	2	4, 6, 8, 10, 12, …, 30
2	3	9, 15, 21, 27 (6, 12, … đã bị gạch)
3	5	25 (10, 15, 20, 30 đã bị gạch)
4	7	7 × 7 = 49 > 30, dừng

Các số còn lại: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 đều là số nguyên tố.

Hai nhận xét giúp sàng nhanh hơn:

Bắt đầu gạch từ p × p. Các bội nhỏ hơn như 2p, 3p, … đã bị gạch bởi các số nguyên tố nhỏ hơn p rồi. Ví dụ với p = 5: 10, 15, 20 đã bị gạch bởi 2 và 3.
Dừng khi p × p > n. Lúc đó không còn bội nào cần gạch.

Cài đặt

Dùng một mảng la_nt đánh dấu: ban đầu coi mọi số là nguyên tố, rồi gạch dần.

Python
C++

n = int(input())
la_nt = [True] * (n + 1)
la_nt[0] = la_nt[1] = False
p = 2
while p * p <= n:
    if la_nt[p]:                         # p chưa bị gạch: p là số nguyên tố
        for boi in range(p * p, n + 1, p):
            la_nt[boi] = False           # gạch bỏ các bội của p
    p += 1
print(sum(la_nt))                        # số lượng số nguyên tố đến n

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> laNt(n + 1, true);
    laNt[0] = laNt[1] = false;
    for (long long p = 2; p * p <= n; p++) {
        if (laNt[p]) {                              // p chưa bị gạch: p là số nguyên tố
            for (long long boi = p * p; boi <= n; boi += p)
                laNt[boi] = false;                  // gạch bỏ các bội của p
        }
    }
    int dem = 0;
    for (int i = 2; i <= n; i++) dem += laNt[i];
    cout << dem << endl;                            // số lượng số nguyên tố đến n
    return 0;
}

Tổng số lần gạch khoảng n × ln(ln n), với n = 10⁷ chỉ khoảng 3 × 10⁷ lần. So với kiểm tra từng số (khoảng n × √n, tức 3 × 10¹⁰ phép thử), sàng nhanh hơn khoảng 1000 lần.

Lưu ý cho Python: vòng lặp gạch bỏ viết bằng for khá chậm với n = 10⁷. Có thể gạch cả dãy bội trong một lệnh bằng phép gán lát cắt:

la_nt = bytearray([1]) * (n + 1)
la_nt[0] = la_nt[1] = 0
p = 2
while p * p <= n:
    if la_nt[p]:
        la_nt[p * p::p] = bytes(len(range(p * p, n + 1, p)))   # gạch cả dãy bội
    p += 1

Cách này nhanh hơn vòng lặp for nhiều lần vì việc gạch được làm bên trong Python (viết bằng C). Các lời giải luyện tập dùng cách viết này.

Đếm nhanh nhiều đoạn: mảng tiền tố

Đề thường hỏi nhiều câu: “từ a đến b có bao nhiêu số nguyên tố?”. Sàng một lần, rồi tạo mảng dem[x] = số lượng số nguyên tố từ 1 đến x. Mỗi câu hỏi trả lời ngay bằng dem[b] - dem[a - 1], giống cách đếm bội số trong đoạn.

x	1	2	3	4	5	6	7	8	9	10
là số nguyên tố		✓	✓		✓		✓
dem[x]	0	1	2	2	3	3	4	4	4	4

Từ 4 đến 10: dem[10] - dem[3] = 4 - 2 = 2 (là 5 và 7).

Sàng ước nguyên tố nhỏ nhất

Thay vì chỉ đánh dấu “bị gạch”, ta ghi lại số nguyên tố nhỏ nhất gạch nó: nho_nhat[x] là ước nguyên tố nhỏ nhất của x. Khi đó phân tích thừa số x chỉ cần chia liên tục cho nho_nhat[x]:

360 → chia 2 → 180 → chia 2 → 90 → chia 2 → 45 → chia 3 → 15 → chia 3 → 5 → chia 5 → 1

Mỗi bước chia ít nhất cho 2, nên chỉ mất khoảng 20 bước với x ≤ 10⁶. Rất hợp khi phải phân tích rất nhiều số.

Python
C++

n = 10 ** 6
nho_nhat = list(range(n + 1))       # ban đầu nho_nhat[x] = x
p = 2
while p * p <= n:
    if nho_nhat[p] == p:            # p là số nguyên tố
        for boi in range(p * p, n + 1, p):
            if nho_nhat[boi] == boi:
                nho_nhat[boi] = p   # p là số nguyên tố đầu tiên gạch boi
    p += 1

x = 360
while x > 1:
    print(nho_nhat[x], end=" ")     # 2 2 2 3 3 5
    x //= nho_nhat[x]

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 1000000;
    vector<int> nhoNhat(n + 1);
    for (int i = 0; i <= n; i++) nhoNhat[i] = i;   // ban đầu nhoNhat[x] = x
    for (long long p = 2; p * p <= n; p++) {
        if (nhoNhat[p] == p) {                     // p là số nguyên tố
            for (long long boi = p * p; boi <= n; boi += p)
                if (nhoNhat[boi] == boi) nhoNhat[boi] = p;
        }
    }
    int x = 360;
    while (x > 1) {
        cout << nhoNhat[x] << " ";                 // 2 2 2 3 3 5
        x /= nhoNhat[x];
    }
    cout << endl;
    return 0;
}

Khi nào dùng sàng, khi nào kiểm tra từng số?

Đề bài	Cách làm
Kiểm tra một số đến 10¹²	thử chia đến √n
Hỏi về mọi số đến khoảng 10⁷	sàng
Số đến 10¹² nhưng trong một đoạn ngắn	sàng đoạn (bài 19)

Lưu ý: sàng cần một mảng n + 1 phần tử. Với n = 10⁷, mảng bool của C++ hay bytearray của Python chiếm khoảng 10 MB, vẫn ổn. Với n = 10⁹ thì không đủ bộ nhớ, phải nghĩ cách khác.

Luyện tập

Gồm 21 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Sàng cơ bản

Bài 1. Đếm số nguyên tố

Nhập số nguyên dương n (n ≤ 10⁷). In ra số lượng số nguyên tố không vượt quá n.

Ví dụ: nhập 100 thì in ra 25.

Kiểm tra: nhập 10000000.

Xem đáp số

664579

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Liệt kê số nguyên tố trong đoạn

Nhập hai số nguyên a, b (1 ≤ a ≤ b ≤ 10⁶). In ra các số nguyên tố trong đoạn từ a đến b theo thứ tự tăng dần, cách nhau một dấu cách. Nếu không có số nào thì in ra 0.

Ví dụ: nhập 10 30 thì in ra 11 13 17 19 23 29.

Kiểm tra: nhập 100 150.

Xem đáp số

101 103 107 109 113 127 131 137 139 149

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Tổng các số nguyên tố

Nhập số nguyên dương n (n ≤ 10⁷). In ra tổng các số nguyên tố không vượt quá n.

Ví dụ: nhập 10 thì in ra 17.

Kiểm tra: nhập 1000000.

Xem đáp số

37550402023

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Số nguyên tố thứ k

Nhập số nguyên dương k (k ≤ 5 × 10⁵). In ra số nguyên tố thứ k (số nguyên tố thứ nhất là 2).

Ví dụ: nhập 5 thì in ra 11.

Kiểm tra: nhập 10000.

Xem đáp số

104729

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Nhiều câu hỏi đếm số nguyên tố

Dòng đầu là số câu hỏi q (q ≤ 10⁵). Mỗi dòng tiếp theo có hai số a, b (1 ≤ a ≤ b ≤ 10⁶). Với mỗi câu hỏi, in ra trên một dòng số lượng số nguyên tố trong đoạn từ a đến b.

Ví dụ:

Nhập	In ra
`2` `1 10` `4 10`	`4` `2`

Kiểm tra: nhập

3
1 1000000
100 1000
999900 1000000

Xem đáp số

78498
143
8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Sàng rồi kiểm tra điều kiện

Bài 6. Cặp sinh đôi đến 10 triệu

Nhập số nguyên dương n (n ≤ 10⁷). Đếm số cặp số nguyên tố sinh đôi (p, p + 2) với p + 2 ≤ n.

Ví dụ: nhập 20 thì in ra 4.

Kiểm tra: nhập 10000000.

Xem đáp số

58980

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Goldbach với số lớn

Nhập số chẵn n (4 ≤ n ≤ 10⁷). Đếm số cặp số nguyên tố (p, q) với p ≤ q và p + q = n.

Ví dụ: nhập 100 thì in ra 6.

Kiểm tra: nhập 1000000.

Xem đáp số

5402

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Số nguyên tố có tổng chữ số nguyên tố

Nhập số nguyên dương n (n ≤ 10⁷). Đếm các số nguyên tố p không vượt quá n mà tổng các chữ số của p cũng là số nguyên tố.

Ví dụ: nhập 30 thì in ra 7.

Kiểm tra: nhập 1000000.

Xem đáp số

30123

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Số nguyên tố Sophie Germain

Số nguyên tố p gọi là số nguyên tố Sophie Germain nếu 2p + 1 cũng là số nguyên tố, ví dụ 11 (vì 23 là số nguyên tố). Nhập số nguyên dương n (n ≤ 10⁶), đếm các số nguyên tố Sophie Germain không vượt quá n.

Ví dụ: nhập 30 thì in ra 6.

Kiểm tra: nhập 1000000.

Xem đáp số

7746

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Số nguyên tố đối xứng đến 10 triệu

Nhập số nguyên dương n (n ≤ 10⁷). Đếm các số không vượt quá n vừa là số nguyên tố, vừa là số đối xứng.

Ví dụ: nhập 1000 thì in ra 20.

Kiểm tra: nhập 10000000.

Xem đáp số

781

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Số nguyên tố xoay vòng

Số nguyên tố xoay vòng là số mà mọi cách xoay vòng các chữ số đều cho số nguyên tố, ví dụ 197 (197, 971, 719 đều là số nguyên tố). Nhập số nguyên dương n (n ≤ 10⁶), đếm các số nguyên tố xoay vòng nhỏ hơn n.

Ví dụ: nhập 100 thì in ra 13.

Kiểm tra: nhập 1000000.

Xem đáp số

55

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Khoảng trống lớn nhất đến 10 triệu

Nhập số nguyên dương n (3 ≤ n ≤ 10⁷). Trong các cặp số nguyên tố liên tiếp p, q không vượt quá n, tìm cặp có hiệu q - p lớn nhất. In ra p và q; nếu có nhiều cặp thì in cặp có p nhỏ nhất.

Ví dụ: nhập 1000 thì in ra 887 907.

Kiểm tra: nhập 10000000.

Xem đáp số

4652353 4652507

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Sàng ước nguyên tố nhỏ nhất

Bài 13. Phân tích nhiều số

Dòng đầu là q (q ≤ 10⁵). Mỗi dòng tiếp theo có một số x (2 ≤ x ≤ 10⁶). Với mỗi x, in ra trên một dòng phân tích thừa số nguyên tố của x theo dạng của bài phân tích thừa số, ví dụ 2^3*3^2*5.

Ví dụ:

Nhập	In ra
`2` `360` `97`	`2^33^25` `97`

Kiểm tra: nhập

Xem đáp số

2^6*5^6
999983
2^4*3^2*5*7*11*13

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Đúng k ước nguyên tố khác nhau

Nhập hai số nguyên dương n, k (n ≤ 10⁶, k ≤ 10). Đếm các số x từ 2 đến n có đúng k ước nguyên tố khác nhau.

Ví dụ: nhập 30 2 thì in ra 12.

Kiểm tra: nhập 1000000 3.

Xem đáp số

379720

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Đếm số nửa nguyên tố

Số nửa nguyên tố là tích của hai số nguyên tố (có thể bằng nhau), ví dụ 4, 6, 9, 10. Nhập số nguyên dương n (n ≤ 10⁶), đếm các số nửa nguyên tố không vượt quá n.

Ví dụ: nhập 30 thì in ra 10.

Kiểm tra: nhập 1000000.

Xem đáp số

210035

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Số trơn

Số k-trơn là số nguyên dương có mọi ước nguyên tố đều không vượt quá k (số 1 cũng được coi là k-trơn). Nhập hai số nguyên dương n, k (2 ≤ k ≤ n ≤ 10⁶), đếm các số k-trơn không vượt quá n.

Ví dụ: nhập 30 3 thì in ra 12.

Kiểm tra: nhập 1000000 7.

Xem đáp số

1273

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Số ước của nhiều số

Dòng đầu là q (q ≤ 10⁵). Mỗi dòng tiếp theo có một số x (1 ≤ x ≤ 10⁶). Với mỗi x, in ra trên một dòng số ước của x.

Ví dụ:

Nhập	In ra
`3` `1` `12` `36`	`1` `6` `9`

Kiểm tra: nhập

Xem đáp số

24
240
2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Mở rộng cách sàng

Bài 18. Số có số ước là số nguyên tố

Nhập số nguyên dương n (n ≤ 10⁶). Đếm các số x từ 1 đến n mà số ước của x là một số nguyên tố.

Ví dụ: nhập 20 thì in ra 11.

Kiểm tra: nhập 1000000.

Xem đáp số

78687

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Sàng đoạn

Nhập hai số nguyên L, R (2 ≤ L ≤ R ≤ 10¹², R - L ≤ 10⁶). Đếm số nguyên tố trong đoạn từ L đến R.

Ví dụ: nhập 100 200 thì in ra 21.

Kiểm tra: nhập 999999000000 1000000000000.

Xem đáp số

36400

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Đếm phân số tối giản

Nhập số nguyên dương n (n ≤ 10⁶). Với mỗi x từ 1 đến n, gọi f(x) là số lượng số y từ 1 đến x mà y và x không có ước chung nào lớn hơn 1 (ví dụ f(6) = 2 vì chỉ có 1 và 5). In ra f(1) + f(2) + … + f(n).

Ví dụ: nhập 10 thì in ra 32.

Kiểm tra: nhập 1000000.

Xem đáp số

303963552392

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 21. Tổng ước nguyên tố

Với mỗi x, gọi g(x) là tổng các ước nguyên tố khác nhau của x (g(12) = 2 + 3 = 5, g(1) = 0). Nhập số nguyên dương n (n ≤ 10⁷), in ra g(1) + g(2) + … + g(n).

Ví dụ: nhập 10 thì in ra 36.

Kiểm tra: nhập 1000000.

Xem đáp số

64986402084

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English