Elearning CodePath – CTP Online Judge

Tìm K Chữ số nguyên tố trong đoạn [A, B]

CSNTO

🟢 Hard #General #Math #Number Theory

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho đoạn $[A, B]$ (với $A, B$ là các số nguyên dương).
Yêu cầu: Tìm số lượng số nguyên tố $P$ thỏa mãn đồng thời hai điều kiện sau:
1.  $P$ nằm trong đoạn $[A, B]$ (tức là $A \le P \le B$).
2.  $P$ là số có đúng $K$ chữ số.

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `CSNTO.INP`:

* Gồm một dòng duy nhất: Chứa ba số nguyên $K$, $A$, và $B$, cách nhau bởi dấu cách.

Giới hạn:
* $A, B \le 10^6$.
* $K$ là số nguyên dương.

---
### 📤 Định dạng Đầu ra

Ghi ra file `CSNTO.OUT` một số nguyên duy nhất là số lượng số nguyên tố cần tìm.

---
### ✨ Ví dụ

| Input (`CSNTO.INP`) | Output (`CSNTO.OUT`) |
| :--- | :--- |
| `1 2 10` | `4` |

Giải thích:
* $K=1$, $A=2, B=10$.
* Các số có 1 chữ số trong đoạn $[2, 10]$ là $\{2, 3, 4, 5, 6, 7, 8, 9\}$.
* Các số nguyên tố có 1 chữ số là $\{2, 3, 5, 7\}$.
* Số lượng: 4.

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $A, B \le 10^3$ | $30\%$ |
| 2 | $A, B \le 10^5$ | $40\%$ |
| 3 | $A, B \le 10^6$ | $30\%$ |

---

✅ Đã AC: 7 / 20 submissions

📘 Lời giải

### Bài toán: Đếm số nguyên tố có $K$ chữ số trong đoạn $\left[A, B\right]$ (CSNTO)

### I. Subtask 1: $A, B \le 10^3$ (30% điểm)

#### 1. Dùng phương pháp Vét cạn (Trial Division)

Với giới hạn nhỏ $B \le 10^3$, số lượng số cần kiểm tra trong đoạn $\left[A, B\right]$ tối đa là $10^3$.

Độ phức tạp của việc kiểm tra tính nguyên tố bằng **Trial Division** cho một số $P$ là $O(\sqrt{P})$.

Tổng độ phức tạp tối đa là $O((B-A) \cdot \sqrt{B}) \le O(10^3 \cdot \sqrt{10^3}) \approx 32,000$ phép tính.Do số lượng phép tính rất thấp, phương pháp vét cạn này đảm bảo chạy nhanh chóng và là lựa chọn đơn giản nhất cho Subtask 1.

#### **Code (1):**
```
#include <bits/stdc++.h>

using namespace std;

// Hàm kiểm tra số nguyên tố bằng Trial Division
// Độ phức tạp: O(sqrt(n))
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    
    // Tối ưu: Loại bỏ các bội của 2 và 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    
    // Kiểm tra các ước số có dạng 6k +/- 1, đến căn bậc hai của n
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

// Hàm giải quyết bài toán cho Subtask 1 (N <= 10^3)
void solve_subtask1() {
    int K, A, B;
    // Đọc K (số chữ số), A và B (giới hạn đoạn)
    if (!(cin >> K >> A >> B)) return;

// 1. Xác định giới hạn của số có K chữ số: [L, R]
    // Công thức: $L = 10^{K-1}$ và $R = 10^K - 1$
    long long L = 1;
    for (int i = 0; i < K - 1; ++i) {
        L *= 10;
    }
    long long R = L * 10 - 1;

// 2. Xác định phạm vi cuối cùng cần đếm: [Start, End]
    // Phạm vi này là giao của $[A, B]$ và $[L, R]$
    int Start = max((long long)A, L);
    int End = min((long long)B, R);

int count = 0;
    
    // 3. Vét cạn và kiểm tra từng số trong đoạn [Start, End]
    // Độ phức tạp của bước này: O((B-A) * sqrt(B)), chấp nhận được khi B <= 10^3
    if (Start <= End) {
        for (int i = Start; i <= End; ++i) {
            if (isPrime(i)) {
                count++;
            }
        }
    }
    
    cout << count << endl;
}

int main() {
    // Tối ưu hóa I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve_subtask1();
    return 0;
}

```
---

### II. Subtask 2 & 3: $A, B \le 10^6$ (70% điểm còn lại)

#### 1. Giải thích Phương pháp Tối ưu (Sàng Eratosthenes)

*Nếu tiếp tục dùng Trial Division* (cách giải Subtask 1) cho giới hạn $B \le 10^6$:

Tổng độ phức tạp là $O(B \cdot \sqrt{B}) \approx 10^6 \cdot \sqrt{10^6} = 10^9$ phép tính. Con số này dẫn đến **TLE** (Time Limit Exceeded).

**Sàng Eratosthenes** là thuật toán tiền xử lý. Nó chỉ cần chạy một lần duy nhất với độ phức tạp $O(B  \log B)$. Với $B=10^6$, tổng số phép tính chỉ khoảng $1.5 \times 10^6$.Sau khi Sàng, việc kiểm tra tính nguyên tố của một số bất kỳ trong đoạn $\left[\max(A, L), \min(B, R)\right]$ chỉ mất $O(1)$ (tra cứu trong mảng `is_prime`).

**Tóm tắt:** Ta chuyển từ việc thực hiện $O(\sqrt{B})$ phép tính cho mỗi số sang $O(1)$ phép tính, làm cho tổng thời gian chạy cực kỳ nhanh và giải quyết được tất cả các Subtask.

#### 2. Code Tối ưu (Sàng Eratosthenes)
```
#include <bits/stdc++.h>

using namespace std;

// Giới hạn tối đa của B trong đề bài là 10^6.
const int MAX_B = 1000000;
// Mảng Sàng: is_prime[i] = true nếu i là số nguyên tố
vector<bool> is_prime(MAX_B + 1, true);

// Bước 1: Sàng Eratosthenes để tìm tất cả số nguyên tố <= MAX_B
void sieve() {
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= MAX_B; p++) {
        if (is_prime[p]) {
            // Đánh dấu tất cả bội số của p là hợp số
            for (int i = p * p; i <= MAX_B; i += p)
                is_prime[i] = false;
        }
    }
}

int main() {
    // Tối ưu hóa I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

// Chạy Sàng Eratosthenes một lần duy nhất. Độ phức tạp O(MAX_B * log log MAX_B)
    sieve();

int K, A, B;
    // Đọc đầu vào: K (số chữ số), A và B (giới hạn đoạn)
    if (!(cin >> K >> A >> B)) return 0;

// 1. Xác định giới hạn của số có K chữ số: [L, R]
    // Công thức: $L = 10^{K-1}$ và $R = 10^K - 1$
    long long L = 1;
    // Tính 10^(K-1)
    for (int i = 0; i < K - 1; ++i) {
        L *= 10;
    }
    // Tính 10^K - 1
    long long R = L * 10 - 1;

// Đảm bảo Start và End nằm trong phạm vi Sàng $[0, MAX_B]$
    if (Start > MAX_B) {
        cout << 0 << endl; // Nếu Start vượt quá $10^6$
        return 0;
    }
    End = min(End, MAX_B);

// 3. Đếm số lượng số nguyên tố trong đoạn [Start, End]
    int count = 0;
    
    // Nếu phạm vi hợp lệ ($Start \le End$)
    if (Start <= End) {
        for (int i = Start; i <= End; ++i) {
            // Kiểm tra trong mảng Sàng $O(1)$
            if (is_prime[i]) {
                count++;
            }
        }
    }
    
    cout << count << endl;

return 0;
}
```