1. Tóm tắt đề bài

Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~). Hãy đếm xem trong đoạn ~[a, b]~ có bao nhiêu số mà tổng các chữ số của nó là một số nguyên tố.

• Dữ liệu vào (Input):
  • Một dòng chứa hai số nguyên dương ~a, b~ cách nhau bởi dấu cách (~1 \le a \le b \le 10^4~).
• Dữ liệu ra (Output):
  • Một số nguyên duy nhất là số lượng số tìm được.

2. Phân tích bài toán & Giới hạn

• Giới hạn bài toán:
  • ~a, b \le 10^4~.
  • Số lượng số cần xét trong đoạn ~[a, b]~ tối đa là ~10^4~ số.
  • Với mỗi số ~x \le 10^4~:
    • Giá trị chữ số lớn nhất có thể đạt được là số ~9999~ với tổng chữ số ~9 + 9 + 9 + 9 = 36~ (hoặc với ~100000~ có tổng là ~1~).
    • Do đó, tổng các chữ số của một số thuộc đoạn ~[1, 10^4]~ luôn nằm trong khoảng ~[1, 36]~.
• Phạm vi kiểm tra số nguyên tố:
  • Vì tổng các chữ số nhỏ hơn hoặc bằng ~36~, việc kiểm tra một số có phải số nguyên tố hay không cực kỳ nhẹ và có thể viết một hàm kiểm tra đơn giản chạy với độ phức tạp ~\mathcal{O}(\sqrt{S})~ với ~S \le 36~.
• Đánh giá thời gian & Bộ nhớ:
  • Việc duyệt từng số từ ~a~ đến ~b~, tính tổng chữ số và kiểm tra tính nguyên tố sẽ tốn không quá ~10^4 \times \mathcal{O}(\text{số chữ số} + \sqrt{36}) \approx 10^5~ phép tính. Thời gian chạy hoàn toàn tức thì (~< 0.01~ giây).

3. Thuật toán xử lý

• Ý tưởng:

  1. Xây dựng hàm kiểm tra một số nguyên ~n~ có phải số nguyên tố hay không (isPrime(int n)):
     • Nếu ~n < 2~: trả về false.
     • Duyệt ~i~ từ ~2~ đến ~\sqrt{n}~ (i * i <= n), nếu ~n~ chia hết cho ~i~ thì trả về false.
     • Nếu không có ước nào thỏa mãn, trả về true.
  2. Xây dựng hàm tính tổng các chữ số của một số nguyên dương ~n~ (tongChuSo(int n)):
     • Khởi tạo biến sum = 0.
     • Sử dụng vòng lặp while (n > 0), lấy chữ số hàng đơn vị n % 10 cộng dồn vào sum, sau đó bỏ chữ số cuối bằng n /= 10.
     • Trả về giá trị sum.
  3. Trong hàm main:
     • Khai báo hai biến ~a, b~ và biến đếm dem = 0.
     • Nhập dữ liệu chuẩn: cin >> a >> b;.
     • Duyệt vòng lặp for với biến ~i~ chạy từ ~a~ đến ~b~:
       • Tính tổng các chữ số của ~i~.
       • Nếu tổng này là số nguyên tố thì tăng biến dem lên 1.
     • In kết quả dem ra màn hình và xuống dòng bằng cout << endl;.

• Độ phức tạp:

  • Thời gian: ~\mathcal{O}((b - a + 1) \cdot \log_{10}(b))~ — Duyệt qua các số trong đoạn ~[a, b]~, mỗi số mất vài phép toán để tách chữ số. Chạy cực nhanh trong thời gian ~< 0.01~ giây.
  • Không gian (bộ nhớ): ~\mathcal{O}(1)~ — Chỉ dùng các biến đơn lẻ.

4. Mã nguồn cài đặt (C++)

#include <bits/stdc++.h>
using namespace std;
// Hàm kiểm tra số nguyên tố

bool isPrime(int n) 
{
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) 
        if (n % i == 0) 
            return false;
    return true;
}

// Hàm tính tổng các chữ số của một số nguyên dương
int tongChuSo(int n) 
{
    int sum = 0;
    while (n > 0) 
    {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
int main() 
{
    int a, b;
    cin >> a >> b;
    int dem = 0;
    for (int i = a; i <= b; i++) 
    {
        int tong = tongChuSo(i);
        if (isPrime(tong)) 
            dem++;
    }
    cout << dem << endl;
    return 0;

}