Tóm tắt đề bài

Một số \(P\) gọi là nguyên tố đặc biệt nếu:

• \(P\) là số nguyên tố
• Tổng các chữ số của \(P\) cũng là số nguyên tố

Cho dãy \(A\) gồm \(n\) số (\(n \le 10^6\), \(a_i \le 10^6\)). Hãy đếm có bao nhiêu phần tử trong dãy là nguyên tố đặc biệt.

Phân tích

• Giới hạn \(a_i \le 10^6\) cho phép ta tiền xử lý tính nguyên tố cho mọi số đến \(10^6\) bằng sàng Eratosthenes.
• Với mỗi số \(a_i\):
  • Kiểm tra \(a_i\) có nguyên tố không trong \(O(1)\) nhờ mảng isPrime.
  • Tính tổng chữ số \(s(a_i)\) trong \(O(\log_{10} a_i)\) (tối đa 7 chữ số vì \(10^6\)).
  • Kiểm tra \(s(a_i)\) có nguyên tố không.
• Tổng chữ số lớn nhất của số \(\le 10^6\) là \(9 \times 7 = 63\), rất nhỏ.
  • Ta có thể:
    • Dùng luôn isPrime (vì đã sàng đến \(10^6\)), hoặc
    • Sàng đến \(63\) (nhưng không cần thiết).

Bẫy thường gặp:

• \(1\) không phải số nguyên tố.
• Cần I/O nhanh vì \(n\) có thể lên tới \(10^6\).

Hướng giải quyết

Nhận xét

Ta cần trả lời nhiều truy vấn “\(x\) có nguyên tố không?” với \(x \le 10^6\), nên sàng Eratosthenes là lựa chọn tối ưu.

Thuật toán

1. Đọc \(n\).
2. Sàng Eratosthenes tạo mảng isPrime[0..10^6].
3. Với từng \(a_i\):
   • Nếu isPrime[a_i] == false thì bỏ qua.
   • Tính \(s =\) tổng chữ số của \(a_i\).
   • Nếu isPrime[s] == true thì tăng đáp án.
4. In đáp án.

Độ phức tạp

• Thời gian:
  • Sàng: \(O(M \log \log M)\) với \(M = 10^6\)
  • Duyệt mảng: \(O(n \log M)\) (mỗi số tối đa vài chữ số)
• Bộ nhớ: \(O(M)\) cho mảng `isPrime## Tóm tắt đề bài
  Một số \(P\) được gọi là nguyên tố đặc biệt nếu:
• \(P\) là số nguyên tố
• Tổng các chữ số của \(P\) cũng là số nguyên tố

Cho dãy \(A\) gồm \(n\) số nguyên dương (\(n \le 10^6\), \(a_i \le 10^6\)). Hãy đếm có bao nhiêu phần tử trong dãy là nguyên tố đặc biệt.

Phân tích

• Giới hạn \(a_i \le 10^6\) cho phép ta tiền xử lý tính nguyên tố cho mọi số trong \([0..10^6]\) bằng sàng Eratosthenes.
• Với mỗi \(a_i\), ta cần kiểm tra 2 điều kiện:
  • \(a_i\) nguyên tố
  • \(s(a_i)\) nguyên tố, với \(s(x)\) là tổng chữ số của \(x\)
• Tổng chữ số lớn nhất khi \(a_i \le 10^6\) là \(9+9+9+9+9+9+9 = 63\) (nếu tính cả \(10^6\) là 7 chữ số). Vì vậy chỉ cần biết tính nguyên tố đến \(63\) là đủ, nhưng để đơn giản ta có thể dùng luôn mảng sàng đến \(10^6\).

Mục tiêu: \(O(\text{MAX} \log \log \text{MAX} + n)\) với \(\text{MAX}=10^6\).

Hướng giải quyết

Nhận xét

• Nếu làm kiểm tra nguyên tố bằng chia thử cho từng \(a_i\) thì với \(n\) lớn (\(10^6\)) sẽ dễ bị TLE.
• Sàng Eratosthenes tạo mảng isPrime[x] để kiểm tra nguyên tố trong \(O(1)\) cho mỗi phần tử.

Thuật toán

1. Đọc \(n\) và dãy \(A\).
2. Dùng sàng Eratosthenes tạo mảng isPrime cho mọi số từ \(0\) đến \(10^6\).
3. Với từng phần tử \(a_i\):
   • Nếu isPrime[a_i] là false thì bỏ qua.
   • Tính \(t = s(a_i)\) (tổng chữ số).
   • Nếu isPrime[t] là true thì tăng đáp án.
4. In ra đáp án.

Lưu ý/Pitfall thường gặp

• Nhớ đặt isPrime[0] = isPrime[1] = false.
• Dùng I/O nhanh vì \(n\) có thể tới \(10^6\).
• Kiểu dữ liệu đáp án nên là int vẫn đủ (tối đa \(10^6\)), nhưng dùng long long cũng an toàn.

Độ phức tạp

• Thời gian:
  • Sàng: \(O(\text{MAX} \log \log \text{MAX})\)
  • Duyệt dãy và tính tổng chữ số: \(O(n \cdot \text{số chữ số}) \approx O(n)\)
• Bộ nhớ: \(O(\text{MAX})\) cho mảng nguyên tố, với \(\text{MAX}=10^6\).

Code tham khảo

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

static const int MAXA = 1000000;

int digitSum(int x) {
    int s = 0;
    while (x > 0) {
        s += x % 10;
        x /= 10;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Sàng Eratosthenes
    vector<bool> isPrime(MAXA + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; 1LL * i * i <= MAXA; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= MAXA; j += i) {
                isPrime[j] = false;
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (!isPrime[x]) continue;

        int s = digitSum(x);
        if (isPrime[s]) ans++;
    }

    cout << ans << "\n";
    return 0;
}