จำนวนเฉพาะขั้นต่ำของจำนวนเฉพาะหลักเดียวที่ต้องการซึ่งผลรวมเท่ากับ N ใน C++

คำชี้แจงปัญหา

หาจำนวนขั้นต่ำของจำนวนเฉพาะหลักเดียวที่ต้องการซึ่งผลรวมจะเท่ากับ 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