Số lượng số nguyên tố một chữ số tối thiểu có tổng bằng N trong C++

Đề bài

Tìm số lượng số nguyên tố một chữ số tối thiểu cần thiết để tổng của chúng bằng N.

Ví dụ

Nếu N = 9 thì cần 2 số nguyên tố là 7 và 2 để tổng thành 9.

Ví dụ

#include <iostream>
using namespace std;
bool isValidIndex(int i, int val) {
    return (i - val) < 0 ? false : true;
}
int getMinPrimes(int n) {
    int arr[n + 1];
    for (int i = 1; i <= n; ++i) {
        arr[i] = 1000000000L;
    }
    arr[0] = arr[2] = arr[3] = arr[5] = arr[7] = 1;
    for (int i = 1; i <= n; ++i) {
        if (isValidIndex(i, 2)) {
            arr[i] = min(arr[i], 1 + arr[i - 2]);
        }
        if (isValidIndex(i, 3)) {
            arr[i] = min(arr[i], 1 + arr[i - 3]);
        }
        if (isValidIndex(i, 5)) {
            arr[i] = min(arr[i], 1 + arr[i - 5]);
        }
        if (isValidIndex(i, 7)) {
            arr[i] = min(arr[i], 1 + arr[i - 7]);
        }
    }
    return arr[n] == 1000000000L ? -1 : arr[n];
}
int main() {
    int n = 9;
    int result = getMinPrimes(n);
    if (result != -1) {
        cout << "Số nguyên tố tối thiểu cần: " << getMinPrimes(n) << endl;
    } else {
        cout << "Không thể tạo tổng yêu cầu" << endl;
    }
    return 0;
}

Kết quả

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau:

Số nguyên tố tối thiểu cần: 2