Lộ trình Sàng số nguyên tố giúp học viên nắm vững cách tìm và xử lý số nguyên tố hiệu quả trong lập trình thi đấu. Bắt đầu từ kiểm tra nguyên tố cơ bản, học viên sẽ lần lượt làm chủ Sàng Eratosthenes, sàng tối ưu, mảng ước nguyên tố nhỏ nhất, Sàng tuyến tính và các ứng dụng quan trọng trong phân tích thừa số, đếm số nguyên tố và xử lý truy vấn.

Đăng nhập để tham gia lộ trình luyện tập

Some problems in the training are missing or you do not have permission to view them.

70, 71, 72

Lộ trình Sàng số nguyên tố

Số nguyên tố là một trong những chủ đề nền tảng quan trọng của Lý thuyết số trong lập trình thi đấu. Rất nhiều bài toán không chỉ yêu cầu kiểm tra một số có phải số nguyên tố hay không, mà còn yêu cầu xử lý hàng nghìn hoặc hàng triệu giá trị trong cùng một lần chạy chương trình.

Nếu kiểm tra từng số độc lập bằng phép thử chia, lời giải có thể trở nên quá chậm. Khi đó, kỹ thuật sàng số nguyên tố cho phép tiền xử lý đồng thời một khoảng số và trả lời các truy vấn sau đó rất nhanh.

Lộ trình này được xây dựng theo hướng:

hiểu bản chất → cài đặt đúng → tối ưu → ứng dụng → biến thể nâng cao.

Mục tiêu của lộ trình

Sau khi hoàn thành lộ trình, học viên cần có khả năng:

  • hiểu chính xác định nghĩa số nguyên tố và hợp số;
  • kiểm tra một số có phải số nguyên tố trong O(n)O(\sqrt n);
  • xây dựng Sàng Eratosthenes;
  • hiểu vì sao chỉ cần xét các số đến n\sqrt n;
  • hiểu vì sao khi sàng từ số nguyên tố pp có thể bắt đầu từ p2p^2;
  • tìm toàn bộ số nguyên tố không vượt quá nn;
  • đếm số nguyên tố trong một đoạn;
  • xây dựng mảng đánh dấu số nguyên tố;
  • xây dựng mảng ước nguyên tố nhỏ nhất;
  • phân tích một số thành thừa số nguyên tố nhanh sau tiền xử lý;
  • tính số lượng ước và tổng các ước từ phân tích thừa số nguyên tố;
  • làm quen với Sàng tuyến tính;
  • xử lý các bài toán có nhiều truy vấn liên quan đến số nguyên tố;
  • nhận biết khi nào nên dùng kiểm tra nguyên tố, Sàng Eratosthenes, SPF, Sàng tuyến tính hoặc sàng đoạn.

Phần 1. Nền tảng về số nguyên tố

Trước khi học sàng, cần nắm chắc:

  • ước và bội;
  • số nguyên tố;
  • hợp số;
  • phân tích thừa số nguyên tố;
  • căn bậc hai;
  • phép chia lấy dư;
  • độ phức tạp thuật toán.

Một số nguyên p>1p > 1 là số nguyên tố nếu pp chỉ có đúng hai ước dương:

1 vaˋ p.1 \text{ và } p.

Ví dụ:

  • 2,3,5,7,11,132,3,5,7,11,13 là các số nguyên tố;
  • 11 không phải số nguyên tố;
  • 4,6,8,9,104,6,8,9,10 là hợp số.

Phần 2. Kiểm tra nguyên tố bằng thử chia

Cách đơn giản nhất là thử xem nn có chia hết cho số nào từ 22 đến n−1n-1 hay không.

Cách này có độ phức tạp O(n)O(n) và chỉ phù hợp với dữ liệu nhỏ.

Ta có thể cải tiến bằng nhận xét:

Nếu nn là hợp số thì tồn tại hai số nguyên a,b>1a,b > 1 sao cho

n=a×b.n = a \times b.

Ít nhất một trong hai số a,ba,b không vượt quá n\sqrt n.

Vì vậy chỉ cần thử các ước đến n\sqrt n.

Độ phức tạp giảm còn:

O(n).O(\sqrt n).

Đây là phương pháp phù hợp khi chỉ cần kiểm tra một hoặc một vài số.

Phần 3. Sàng Eratosthenes

Khi cần xác định trạng thái nguyên tố của tất cả các số từ 11 đến nn, kiểm tra từng số bằng O(n)O(\sqrt n) không còn hiệu quả.

Sàng Eratosthenes xử lý toàn bộ đoạn:

2,3,…,n2,3,\ldots,n

trong khoảng:

O(nlog⁡log⁡n).O(n\log\log n).

Ý tưởng:

  1. Ban đầu xem mọi số từ 22 trở đi là số nguyên tố.
  2. Xét lần lượt từng số pp.
  3. Nếu pp chưa bị loại thì pp là số nguyên tố.
  4. Loại các bội của pp.
  5. Tiếp tục cho đến khi p2>np^2 > n.

Ví dụ với n=20n=20, các số nguyên tố thu được là:

2,3,5,7,11,13,17,19.2,3,5,7,11,13,17,19.

Đây là thuật toán sàng quan trọng nhất và phải được cài đặt thành thạo.

Phần 4. Tối ưu Sàng Eratosthenes

Khi xử lý số nguyên tố pp, không cần bắt đầu loại từ 2p2p.

Các số

2p,3p,…,(p−1)p2p,3p,\ldots,(p-1)p

đã được xử lý bởi những số nhỏ hơn.

Do đó có thể bắt đầu từ:

p2.p^2.

Ta cũng chỉ cần thực hiện bước sàng với các pp thỏa mãn:

p2≤n.p^2 \le n.

Đây là hai tối ưu cơ bản cần hiểu rõ thay vì chỉ ghi nhớ công thức.

Phần 5. Đếm số nguyên tố

Sau khi có mảng đánh dấu nguyên tố, ta có thể đếm số lượng số nguyên tố không vượt quá nn.

Tiếp tục xây dựng mảng cộng dồn:

cnt[i]=cnt[i−1]+[i laˋ soˆˊ nguyeˆn toˆˊ].cnt[i] = cnt[i-1] + [i\text{ là số nguyên tố}].

Khi đó số lượng số nguyên tố trong đoạn [L,R][L,R] là:

cnt[R]−cnt[L−1].cnt[R] - cnt[L-1].

Sau tiền xử lý, mỗi truy vấn được trả lời trong O(1)O(1).

Đây là một dạng kết hợp quan trọng giữa:

Sàng số nguyên tố + Prefix Sum.

Phần 6. Ước nguyên tố nhỏ nhất

Thay vì chỉ lưu một số có phải nguyên tố hay không, ta có thể lưu:

spf[x]=ước nguyeˆn toˆˊ nhỏ nhaˆˊt của x.spf[x] = \text{ước nguyên tố nhỏ nhất của } x.

Ví dụ:

spf[12]=2,spf[12]=2, spf[15]=3,spf[15]=3, spf[49]=7.spf[49]=7.

Nếu pp là số nguyên tố thì:

spf[p]=p.spf[p]=p.

Mảng SPF cho phép phân tích một số thành thừa số nguyên tố rất nhanh sau khi đã tiền xử lý.

Ví dụ:

84=22×3×7.84 = 2^2 \times 3 \times 7.

Ta lần lượt sử dụng:

$$84 \rightarrow 42 \rightarrow 21 \rightarrow 7 \rightarrow 1.$$

SPF đặc biệt hữu ích trong các bài có nhiều truy vấn phân tích thừa số nguyên tố.

Phần 7. Ứng dụng của phân tích thừa số nguyên tố

Nếu

n=p1a1p2a2⋯pkak,n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},

thì số lượng ước dương của nn là:

d(n)=(a1+1)(a2+1)⋯(ak+1).d(n)=(a_1+1)(a_2+1)\cdots(a_k+1).

Tổng các ước dương của nn là:

$$\sigma(n)= (1+p_1+\cdots+p_1^{a_1}) (1+p_2+\cdots+p_2^{a_2}) \cdots (1+p_k+\cdots+p_k^{a_k}).$$

Vì vậy sàng không chỉ dùng để tìm số nguyên tố mà còn là bước tiền xử lý cho nhiều bài toán lý thuyết số khác.

Phần 8. Sàng tuyến tính

Sàng tuyến tính, còn được gọi là Linear Sieve, có thể xây dựng danh sách số nguyên tố trong:

O(n).O(n).

Ý tưởng quan trọng của phương pháp là đảm bảo mỗi hợp số được sinh ra theo một cách có kiểm soát, thường thông qua ước nguyên tố nhỏ nhất của nó.

Ngoài danh sách số nguyên tố, Sàng tuyến tính còn rất thuận lợi khi cần tính đồng thời các hàm số học như:

  • ước nguyên tố nhỏ nhất;
  • số lượng thừa số nguyên tố;
  • hàm Euler φ(n)\varphi(n);
  • hàm Möbius μ(n)\mu(n).

Ở giai đoạn đầu, học viên cần ưu tiên hiểu và thành thạo Sàng Eratosthenes trước khi chuyển sang Sàng tuyến tính.

Phần 9. Sàng đoạn

Khi cần tìm các số nguyên tố trong đoạn:

[L,R][L,R]

nhưng RR quá lớn để tạo mảng kích thước RR, có thể sử dụng Segmented Sieve.

Ta chỉ cần sàng trước các số nguyên tố đến:

R,\sqrt R,

sau đó dùng chúng để loại các hợp số trong đoạn [L,R][L,R].

Kỹ thuật này đặc biệt hữu ích khi:

  • RR rất lớn;
  • độ dài đoạn R−L+1R-L+1 không quá lớn;
  • không thể tạo một mảng từ 11 đến RR.

Thứ tự học đề nghị

Học viên nên hoàn thành các phần theo đúng thứ tự:

  1. Ước, bội và số nguyên tố.
  2. Kiểm tra nguyên tố bằng thử chia.
  3. Tối ưu kiểm tra đến n\sqrt n.
  4. Sàng Eratosthenes cơ bản.
  5. Tối ưu sàng từ p2p^2.
  6. Liệt kê số nguyên tố.
  7. Đếm số nguyên tố.
  8. Sàng kết hợp Prefix Sum.
  9. Phân tích thừa số nguyên tố.
  10. Mảng SPF.
  11. Các hàm dựa trên phân tích thừa số.
  12. Sàng tuyến tính.
  13. Sàng đoạn.
  14. Bài toán tổng hợp và bài thi lập trình.

Kỹ năng cần đạt

Không nên xem là hoàn thành lộ trình nếu chỉ thuộc mã nguồn của Sàng Eratosthenes.

Học viên cần tự giải thích được:

  • tại sao 11 không phải số nguyên tố;
  • tại sao chỉ cần kiểm tra đến n\sqrt n;
  • tại sao Sàng Eratosthenes có thể bắt đầu loại từ p2p^2;
  • tại sao chỉ cần sàng với p2≤np^2 \le n;
  • sự khác nhau giữa kiểm tra nguyên tố và sàng số nguyên tố;
  • khi nào cần dùng SPF;
  • khi nào Sàng tuyến tính có lợi;
  • khi nào phải chuyển sang Sàng đoạn;
  • cách kết hợp sàng với Prefix Sum để xử lý nhiều truy vấn.

Mục tiêu cuối cùng là khi gặp một bài toán liên quan đến số nguyên tố, học viên có thể nhanh chóng xác định đúng dạng tiền xử lý và lựa chọn thuật toán phù hợp với giới hạn dữ liệu.

Phần 1. Các Bài Toán Nhập Môn

Mở

Bài toán Tried AC Độ khó
70   *(Ẩn) 0 0 (Không có)
71   *(Ẩn) 0 0 (Không có)
72   *(Ẩn) 0 0 (Không có)
 
Người tham gia
1
Tạo bởi
  1. Danh sách tác vụ
  1. Language
  2. Chế độ cũ
  3. Giao diện
  3. Worker 0, 30ms
  4. Powered by Hydro v5.0.4 Community