Tổng các số có tổng chữ số là số nguyên tố

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

// Function to generate all prime numbers
// that are less than or equal to n
void SieveOfEratosthenes(int n, bool prime[]) {
    prime[0] = prime[1] = false; // 0 và 1 không phải số nguyên tố
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == true) { // Nếu p là số nguyên tố
            for (int i = p * p; i <= n; i += p) // Đánh dấu tất cả bội số của p
                prime[i] = false; // Không phải số nguyên tố
        }
    }
}

// Function to find the count of N-digit numbers
// such that the sum of digits is a prime number
int countOfNumbers(int N) {
    // Stores the dp states
    int dp[N + 1][1000];

    // Initializing dp array with 0
    memset(dp, 0, sizeof(dp));

    // Initializing prime array to true
    bool prime[1005];
    memset(prime, true, sizeof(prime));

    // Find all primes less than or equal to 1000,
    // which is sufficient for N up to 100
    SieveOfEratosthenes(1000, prime);

    // Base cases
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1; // Chỉ có các số từ 1 đến 9 là hợp lệ cho số 1 chữ số

    if (N == 1)
        dp[1][0] = 1; // Nếu N = 1, có một số hợp lệ là 0

    // Fill the dp table
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j <= 900; j++) {
            for (int k = 0; k <= 9; k++) {
                dp[i][j + k] += dp[i - 1][j]; // Cộng số cách cho các số có tổng các chữ số là j
            }
        }
    }

    int ans = 0;
    for (int i = 2; i <= 900; i++) {
        if (prime[i]) // Kiểm tra xem tổng có phải là số nguyên tố không
            ans += dp[N][i]; // Cộng các cách cho số N chữ số
    }

    // Return the answer
    return ans;
}

// Driver Code
int main() {
    // Given Input
    int N = 5; // Số chữ số cần tìm

    // Function call
    cout << countOfNumbers(N); // In ra kết quả

    return 0;
}