ข้อความโจทย์
หาจำนวนเฉพาะตัวเลขเดียว (single-digit primes) น้อยที่สุดที่จำเป็น ซึ่งผลรวมของพวกเขาเท่ากับ N
ตัวอย่าง
ถ้า N = 9 ต้องการจำนวนเฉพาะ 2 ตัว คือ 7 และ 2 เพื่อให้ผลรวมเป็น 9
ตัวอย่าง
#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 << "Minimum required primes: " << getMinPrimes(n) << endl; } else { cout << "Not possible to create required sum" << endl; } return 0; }ผลลัพธ์
เมื่อคอมไพล์และรันโปรแกรมข้างต้น จะได้ผลลัพธ์ดังนี้
Minimum required primes: 2
