資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中所需單數字素數的最小數量，其和等於 N
問題描述
找出所需單數字素數的最小數量，其和等於 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
更新於： 22-11-2019
159 次檢視
廣告