Đếm Số Nguyên Tố (MK119SNT)

Nguồn: LuyenCode Độ khó: Dễ Số nguyên tố Sàng Eratosthenes Mảng cộng dồn

Đề bài

Cho hai số nguyên dương $L \le R$. Hãy đếm xem trong đoạn $[L, R]$ có bao nhiêu số nguyên tố.

Dữ liệu vào:

• Dòng đầu ghi số nguyên dương $T$ là số bộ test;
• $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $L \le R$ cách nhau bởi một dấu cách.

Giới hạn: $1 \le T \le 10^2$, $1 \le L \le R \le 10^6$.

Dữ liệu ra: Với mỗi cặp số $L$ và $R$, ghi ra trên một dòng số số nguyên tố trong đoạn $[L, R]$.

Ví dụ – input

2
2 3
10 15

Ví dụ – output

2
2

Lời mở đầu

Đây là một bài rất "kinh điển" để luyện tay với số nguyên tố. Đi qua bài này các bạn sẽ thấy rõ một hành trình tối ưu: từ cách vét cạn cỡ $10^{11}$ phép tính, rút xuống 100 triệu, rồi rút xuống chỉ còn cỡ 5 triệu. Đồng thời mình cũng chỉ cho các bạn một dấu hiệu nhận dạng rất hay gặp của dạng bài "nhiều truy vấn trên đoạn" 😇.

Mình giải thích ví dụ mẫu để bạn nào chưa hiểu đề sẽ hiểu rõ. Có $T = 2$ bộ test:

• Đoạn $[2, 3]$ gồm 2 và 3 – cả hai đều là số nguyên tố ⇒ in ra 2.
• Đoạn $[10, 15]$ gồm 10, 11, 12, 13, 14, 15 – chỉ có 11 và 13 là số nguyên tố ⇒ in ra 2.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn, kiểm tra từng số · ~10^11 · TLECách 2Sàng + duyệt đoạn · ~10^8 · sát ngưỡngCách 3Sàng + mảng đếm cộng dồn · ~5·10^6

Cách 1Vét cạn kiểm tra từng số – O(T · (R − L) · √R)

Một cách "ngây thơ" là vét cạn: chạy đủ $T$ bộ test (cái này chắc chắn không tránh được rồi), với mỗi bộ test chạy vòng lặp xét đủ các số trong đoạn từ $L$ đến $R$; với mỗi số gọi hàm kiểm tra tính nguyên tố, nếu thỏa thì tăng biến đếm. Sau cùng in biến đếm ra, rồi qua test tiếp theo, reset biến đếm và lặp lại quy trình như cũ.

Hàm kiểm tra số nguyên tố mình viết theo cách khá tối ưu: chỉ thử chia cho các $i$ với $i \cdot i \le x$, độ phức tạp $O(\sqrt{X})$.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

/* Hàm kiểm tra số nguyên tố với độ phức tạp O(sqrt(X)) */
bool isPrime(int x){
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0){
            return false;
        }
    }
    return x >= 2;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int l, r;
        cin >> l >> r;
        int cnt = 0;
        for(int i = l; i <= r; ++i){
            if(isPrime(i)){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

import sys

# Hàm kiểm tra số nguyên tố với độ phức tạp O(sqrt(X))
def is_prime(x):
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return x >= 2

def main():
    data = sys.stdin.read().split()
    t = int(data[0])
    out = []
    p = 1
    for _ in range(t):
        l, r = int(data[p]), int(data[p + 1])
        p += 2
        cnt = 0
        for i in range(l, r + 1):
            if is_prime(i):
                cnt += 1
        out.append(str(cnt))
    print("\n".join(out))

main()

C++▶ Chạy tay từng dòng codeCách 1: với mỗi số i trong [l, r] gọi isPrime(i) thử chia cho 2, 3, ... đến √i.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 15

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4/* Hàm kiểm tra số nguyên tố với độ phức tạp O(sqrt(X)) */

5bool isPrime(int x){

6 for(int i = 2; i * i <= x; ++i){

7 if(x % i == 0){

8 return false;

9 }

10 }

11 return x >= 2;

12}

13

14int main(){

15 ios::sync_with_stdio(0);

16 cin.tie(0);

17 int t;

18 cin >> t;

19 while(t--){

20 int l, r;

21 cin >> l >> r;

22 int cnt = 0;

23 for(int i = l; i <= r; ++i){

24 if(isPrime(i)){

25 cnt++;

26 }

27 }

28 cout << cnt << endl;

29 }

30 return 0;

31}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$ do chẳng cần dùng thêm mảng phụ gì cả.
• Thời gian: $O(T \cdot (R - L) \cdot \sqrt{R})$: duyệt $T$ bộ test, mỗi bộ test duyệt hết các số từ $L$ đến $R$, mỗi số kiểm tra mất tối đa cỡ $\sqrt{R}$ (giá trị lớn nhất cần kiểm tra chính là $R$). Thử nhẩm trường hợp xấu nhất: $T = 100$ bộ test, bộ nào cũng $L = 1$, $R = 10^6$ ⇒ $10^2 \cdot 10^6 \cdot 10^3 = 10^{11}$. Vượt xa ngưỡng 1 giây ⇒ chắc chắn bị TLE.

Không gian$O(1)$

Thời gian$O(T \cdot (R - L) \cdot \sqrt{R})$

Vét cạn không có gì sai cả

Nếu đề hạ giới hạn xuống, ví dụ $R$ tối đa tầm $10^4$, thì cách trên vẫn có khả năng AC. Và mình nhấn mạnh: nếu giới hạn nằm trong ngưỡng AC được thì mình cũng làm theo cách vét cạn cho đơn giản, nhanh chóng, không phải nặng đầu hehe. Còn với giới hạn hiện tại thì phải vắt óc nghĩ hướng tối ưu hơn.

Cách 2Sàng Eratosthenes rồi duyệt đoạn – O(N log log N + T · (R − L))

Ta nhận ra một cách tốt hơn: thay vì với mỗi giá trị trong đoạn $L..R$ cứ phải liên tục gọi hàm kiểm tra số nguyên tố, ta có thể ngay từ đầu lọc ra, đánh dấu hết những số trong đoạn từ 1 đến $10^6$ xem số nào là số nguyên tố. Bước này dùng sàng nguyên tố Eratosthenes để tạo ra mảng sàng a (a[x] = 0 nghĩa là $x$ nguyên tố, a[x] = 1 nghĩa là không). Rồi với mỗi $i$ trong đoạn $L..R$, chỉ cần nhìn a[i] là biết ngay $i$ có phải số nguyên tố không, từ đó tăng biến đếm.

Ý tưởng sàng Eratosthenes

Đi lần lượt $i = 2, 3, \dots$ với $i \cdot i \lt n$. Nếu $i$ chưa bị gạch (nghĩa là $i$ nguyên tố) thì gạch hết các bội của $i$ bắt đầu từ $i \cdot i$ ($i \cdot i,\ i \cdot i + i,\ \dots$). Những bội nhỏ hơn $i \cdot i$ đã bị gạch bởi các số nguyên tố nhỏ hơn từ trước rồi. Cuối cùng số nào không bị gạch chính là số nguyên tố.

Phải dùng sàng, đừng dùng hàm kiểm tra cho từng số

Lưu ý là phải dùng thuật toán sàng để có độ phức tạp $O(N \log \log N)$ (chấp nhận tốn thêm bộ nhớ $O(N)$ cho mảng đánh dấu). Nếu ta xét lần lượt từ 1 đến $N$ rồi gọi hàm kiểm tra cho từng số thì bước này là $O(N \sqrt{N}) = 10^6 \cdot 10^3 = 10^9$ – cũng TLE, ngang cách trước mà còn tốn thêm bộ nhớ. Còn dùng sàng thì $N \log \log N$ với $N = 10^6$ chỉ cỡ $5 \cdot 10^6$ (5 triệu), thoải mái.

Khung minh hoạ bên dưới cho các bạn xem sàng chạy trên các số nhỏ (bước cuối cùng là phần mảng đếm cho Cách 3, các bạn xem luôn cũng được):

N L R

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này:

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

const int n = 1000001;
int a[n]; // mảng toàn cục: mặc định toàn 0

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    /* Bước sàng nguyên tố Eratosthenes */
    a[0] = a[1] = 1;
    for(int i = 2; i * i < n; ++i){
        if(a[i] == 0){
            for(int j = i * i; j < n; j += i){
                if(a[j] == 0){
                    a[j] = 1;
                }
            }
        }
    }
    /* Bước đọc dữ liệu từng bộ test và xử lý in ra kết quả */
    int t;
    cin >> t;
    while(t--){
        int l, r;
        cin >> l >> r;
        int cnt = 0;
        for(int i = l; i <= r; ++i){
            if(a[i] == 0){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

import sys

n = 1000001
# Bước sàng nguyên tố Eratosthenes (a[x] = 1 nghĩa là x KHÔNG phải số nguyên tố)
a = bytearray(n)
a[0] = a[1] = 1
i = 2
while i * i < n:
    if a[i] == 0:
        a[i * i::i] = b"\x01" * len(range(i * i, n, i))
    i += 1

# Bước đọc dữ liệu từng bộ test và xử lý in ra kết quả
data = sys.stdin.read().split()
t = int(data[0])
out = []
p = 1
for _ in range(t):
    l, r = int(data[p]), int(data[p + 1])
    p += 2
    # đếm số ô bằng 0 trong đoạn [l, r] (vẫn là duyệt O(R - L))
    cnt = a.count(0, l, r + 1)
    out.append(str(cnt))
print("\n".join(out))

Ở khung chạy tay dưới đây, phần sàng trên $10^6$ số mình chỉ cho chạy chi tiết với vài số nguyên tố đầu tiên, phần còn lại gom thành một bước (chứ chạy tay đủ thì cả triệu bước 😅). Kết quả mảng a vẫn là kết quả thật của cả $10^6$ số.

C++▶ Chạy tay từng dòng codeCách 2: sàng Eratosthenes tới 10^6, mỗi truy vấn duyệt i từ l đến r và đếm a[i] == 0.

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 15

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const int n = 1000001;

5int a[n]; // mảng toàn cục: mặc định toàn 0

6

7int main(){

8 ios::sync_with_stdio(0);

9 cin.tie(0);

10 /* Bước sàng nguyên tố Eratosthenes */

11 a[0] = a[1] = 1;

12 for(int i = 2; i * i < n; ++i){

13 if(a[i] == 0){

14 for(int j = i * i; j < n; j += i){

15 if(a[j] == 0){

16 a[j] = 1;

17 }

18 }

19 }

20 }

21 /* Bước đọc dữ liệu từng bộ test và xử lý in ra kết quả */

22 int t;

23 cin >> t;

24 while(t--){

25 int l, r;

26 cin >> l >> r;

27 int cnt = 0;

28 for(int i = l; i <= r; ++i){

29 if(a[i] == 0){

30 cnt++;

31 }

32 }

33 cout << cnt << endl;

34 }

35 return 0;

36}

ChậmVừaNhanhRất nhanh

Mình chỉnh nhẹ code gốc ở 2 chỗ

Bản code mình đăng trên Facebook khai báo int n = 1000001; int a[n] = {0}; bên trong main và cho vòng sàng chạy j <= n. Có 2 điểm nên sửa:

• Mảng chỉ có index $0..n-1$, nên j <= n sẽ chạm tới a[1000001] – ngoài mảng (vì $1000001 = 101 \times 9901$ nên thật sự có lúc gạch đúng vào ô đó). Mình sửa thành i * i < n và j < n.
• Mảng 4 MB khai báo trong main nằm trên stack, một số máy chấm giới hạn stack nhỏ có thể bị lỗi. Đưa ra mảng toàn cục thì an toàn hơn, lại tự động được khởi tạo toàn 0.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ với $N = 10^6 + 1$ cho mảng sàng.
• Thời gian: bước sàng $O(N \log \log N)$ cỡ 5 triệu – ổn. Nhưng bước xử lý tiếp theo vẫn phải xét đủ $T$ bộ test, mỗi bộ test chạy từ $L$ đến $R$: trường hợp xấu nhất $T = 100$, $L = 1$, $R = 10^6$ thì là $O(T \cdot (R - L)) = 10^8$ (100 triệu). Mức này chạm ngưỡng tối đa nên khả năng TLE vẫn còn. Tuy nhiên các bạn có thể thử, biết đâu gặp đúng server chấm mạnh, hoặc test không rơi vào trường hợp xấu nhất thì sao hehe 😁.

Không gian$O(N)$

Thời gian$O(N \log \log N + T \cdot (R - L))$

Cách 3Sàng + mảng đếm cộng dồn – O(N log log N + T)

Dấu hiệu nhận dạng

Với những bài cứ kiểu yêu cầu tìm/đếm trong một đoạn cụ thể và có nhiều truy vấn, phần lớn cách giải là: trước tiên xử lý hết toàn bộ phạm vi đề đưa ra, lưu trữ kết quả lại; sau đó với mỗi truy vấn chỉ việc lấy dữ liệu đã lưu để rút ra kết quả. Mỗi bài sẽ có cách xử lý khác nhau, nhưng các bạn cứ nhớ dấu hiệu và hướng làm này.

Áp vào bài này: đầu tiên vẫn dùng sàng Eratosthenes đánh dấu trong phạm vi 1 đến $10^6$ số nào là số nguyên tố. Rồi ta tạo mảng thống kê số lượng số nguyên tố tính từ 1 trở đi. Ví dụ với 10 giá trị đầu tiên:

i	1	2	3	4	5	6	7	8	9	10
nguyên tố?	–	✔	✔	–	✔	–	✔	–	–	–
a[i]	0	1	2	2	3	3	4	4	4	4

Chẳng hạn a[1] = 0 vì từ 1 đến 1 không có số nguyên tố nào; a[4] = 2 vì từ 1 đến 4 có 2 số nguyên tố (2, 3); a[7] = 4 vì từ 1 đến 7 có 4 số nguyên tố (2, 3, 5, 7); a[10] = 4 vẫn là 2, 3, 5, 7. Tức là a[i] chính là số lượng số nguyên tố trong đoạn từ 1 đến $i$.

Có mảng này rồi thì truy vấn đoạn $[L, R]$ rất đơn giản: lấy a[R] - a[L], rồi xét riêng $L$ có phải số nguyên tố không, nếu có thì cộng thêm 1. Tại sao? Vì a[R] là số lượng số nguyên tố từ 1 đến $R$, a[L] là số lượng từ 1 đến $L$, nên a[R] - a[L] chỉ ra số lượng trong đoạn $L + 1$ đến $R$ – thiếu mất chính $L$.

Ví dụ $L = 3$, $R = 10$: a[10] - a[3] $= 4 - 2 = 2$. Mà $L = 3$ là số nguyên tố nên cộng thêm 1 ⇒ đáp án 3. Nhẩm lại: từ 3 đến 10 có 3, 5, 7 – đúng 3 số ✅. Các bạn cứ thử nhẩm thêm vài trường hợp khác để tự kiểm chứng nhé.

Tối ưu thêm: dùng luôn mảng sàng làm mảng đếm

Ta không cần tạo mảng riêng, mà biến luôn mảng đánh dấu thành mảng đếm. Khi đó kiểm tra $L$ có phải số nguyên tố không chỉ cần so a[L] với a[L - 1]: nếu khác nhau tức là tới $L$ số lượng tăng thêm 1 ⇒ $L$ là số nguyên tố. Vì $L \ge 1$ nên a[L - 1] luôn hợp lệ (dùng tới ô index 0 = 0).

Công thức

$\text{đáp án} = a[R] - a[L] + (a[L] \ne a[L-1]\ ?\ 1 : 0) \;=\; a[R] - a[L-1]$

(Công thức của mình viết dài ra cho các bạn thấy rõ ý "xét riêng $L$"; gọn lại thì nó chính là a[R] - a[L - 1] – đúng kiểu mảng cộng dồn quen thuộc.)

Source code để các bạn tham khảo nếu làm theo hướng này:

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

const int n = 1000001;
int a[n]; // mảng toàn cục: mặc định toàn 0

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    /* Bước sàng nguyên tố Eratosthenes */
    a[0] = a[1] = 1;
    for(int i = 2; i * i < n; ++i){
        if(a[i] == 0){
            for(int j = i * i; j < n; j += i){
                if(a[j] == 0){
                    a[j] = 1;
                }
            }
        }
    }
    /* Biến mảng sàng thành mảng đếm số nguyên tố tính từ 1 */
    int cnt = 0;
    for(int i = 0; i < n; ++i){
        if(a[i] == 0){
            cnt++;
        }
        a[i] = cnt;
    }
    /* Bước đọc dữ liệu từng bộ test và in ra kết quả ngay */
    int t;
    cin >> t;
    while(t--){
        int l, r;
        cin >> l >> r;
        cout << a[r] - a[l] + (a[l] != a[l - 1]) << endl;
    }
    return 0;
}

import sys
from itertools import accumulate

n = 1000001
# Bước sàng nguyên tố Eratosthenes (a[x] = 1 nghĩa là x KHÔNG phải số nguyên tố)
sieve = bytearray(n)
sieve[0] = sieve[1] = 1
i = 2
while i * i < n:
    if sieve[i] == 0:
        sieve[i * i::i] = b"\x01" * len(range(i * i, n, i))
    i += 1

# Biến mảng sàng thành mảng đếm số nguyên tố tính từ 1
# (a[i] = số lượng số nguyên tố trong đoạn 1..i; accumulate cộng dồn cho nhanh)
a = list(accumulate(1 - x for x in sieve))

# Bước đọc dữ liệu từng bộ test và in ra kết quả ngay
data = sys.stdin.read().split()
t = int(data[0])
out = []
p = 1
for _ in range(t):
    l, r = int(data[p]), int(data[p + 1])
    p += 2
    out.append(str(a[r] - a[l] + (a[l] != a[l - 1])))
print("\n".join(out))

C++▶ Chạy tay từng dòng codeCách 3: sàng xong biến a thành mảng đếm, mỗi truy vấn chỉ tính a[r] − a[l] + (a[l] != a[l − 1]) trong O(1).

Dữ liệu vào (stdin) – sửa thoải mái2 2 3 10 15

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4const int n = 1000001;

5int a[n]; // mảng toàn cục: mặc định toàn 0

6

7int main(){

8 ios::sync_with_stdio(0);

9 cin.tie(0);

10 /* Bước sàng nguyên tố Eratosthenes */

11 a[0] = a[1] = 1;

12 for(int i = 2; i * i < n; ++i){

13 if(a[i] == 0){

14 for(int j = i * i; j < n; j += i){

15 if(a[j] == 0){

16 a[j] = 1;

17 }

18 }

19 }

20 }

21 /* Biến mảng sàng thành mảng đếm số nguyên tố tính từ 1 */

22 int cnt = 0;

23 for(int i = 0; i < n; ++i){

24 if(a[i] == 0){

25 cnt++;

26 }

27 a[i] = cnt;

28 }

29 /* Bước đọc dữ liệu từng bộ test và in ra kết quả ngay */

30 int t;

31 cin >> t;

32 while(t--){

33 int l, r;

34 cin >> l >> r;

35 cout << a[r] - a[l] + (a[l] != a[l - 1]) << endl;

36 }

37 return 0;

38}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ với $N = 10^6 + 1$ cho mảng sàng (cũng là mảng đếm).
• Thời gian: bước sàng $O(N \log \log N)$; bước biến mảng sàng thành mảng đếm $O(N)$; bước xử lý truy vấn $O(T)$ với $T \le 10^2$. Tổng cộng $O(N \log \log N) + O(N) + O(T)$, theo quy tắc cộng Big-O lấy thành phần lớn nhất ⇒ $O(N \log \log N)$, cao lắm cỡ 5 triệu phép tính – thỏa ngưỡng 1 giây, chắc chắn AC không sợ TLE nhé.

Không gian$O(N)$

Thời gian$O(N \log \log N + T)$

Cách này chấp nhận tốn thêm bộ nhớ so với cách vét cạn, nhưng độ phức tạp tối ưu hơn rất nhiều. Cùng nhìn lại hành trình tối ưu nào:

10^11→10^8→5·10^6

Các bạn đã thấy cái hay của thuật toán chưa 🥰

Ghi chú của mình: code C++ và Python của cả 3 cách đã được kiểm tra với 300 bộ test ngẫu nhiên (đoạn nhỏ lẫn đoạn gần $10^6$), so với code vét cạn – khớp hết; test biên $[1, 1]$ ra 0, $[1, 10^6]$ ra 78498. Với trường hợp xấu nhất $T = 100$, mọi truy vấn đều là $[1, 10^6]$ (thời gian thực trên máy mình, tính cả khởi động): Cách 1 (C++) chỉ một truy vấn đã mất khoảng 1.2 giây, đủ 100 truy vấn chạy quá 30 giây ⇒ TLE đúng như phân tích; Cách 2 (C++) khoảng 0.7 giây – qua được nhưng đúng là sát ngưỡng; Cách 3 (C++) khoảng 0.2 giây (gần như toàn bộ là thời gian sàng). Bản Python của Cách 2 và Cách 3 mình dùng bytearray, gán lát cắt và accumulate cho nhanh (logic giữ nguyên), chạy khoảng 1.4 giây và 0.6 giây; bản Python Cách 1 chỉ để tham khảo vì chậm hơn nhiều.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇