Index of super-prime
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
Let P1, P2, … ,PN, … be a sequence of prime numbers. Super-prime number is such a prime number that its current number in prime numbers sequence is a prime number too. For example, 3 is a super-prime number, but 7 is not. Index of super-prime for number is 0 iff it is impossible to present it as a sum of few (maybe one) super-prime numbers, and if such presentation exists, index is equal to minimal number of items in such presentation. Your task is to find index of super-prime for given numbers and find optimal presentation as a sum of super-primes.
Input
There is a positive integer number in input. Number is not more than 10000.
Output
Write index I for given number as the first number in line. Write I super-primes numbers that are items in optimal presentation for given number. Write these I numbers in order of non-increasing.
Sample Input
6
Sample Output
23 3
#include#include #include using namespace std;const int maxn = 1000;int Q, Ps[maxn] = {0}, cnt = 0, snt = 0;bool isprime(int p){ if(p == 2) return true; if(p % 2 == 0) return false; for(int i = 3, j= 9; j <= p; i+=2, j = i*i) { if(p %i == 0) return false; } return true;}void init(){ cin >> Q; cnt = 1; for(int i = 3; i <= Q; i++) { if(isprime(i)) { cnt++; if(isprime(cnt)) { Ps[snt++] = i; } } }}bool G[maxn * 10] = {0};int F[maxn * 10] = {0};int P[maxn * 10] = {0};int DP(int x){ if(G[x]) return F[x]; G[x] = true; for(int i = 0; i < snt; i++) { if(x >= Ps[i]) { if(DP(x-Ps[i]) < F[x]) { F[x] = F[x-Ps[i]]; P[x] = Ps[i]; } } } F[x]++; return F[x];}bool cmp(const int & x, const int & y){ return x > y;}void print(int x){ int ans[maxn], cnt = 0; if(P[x] == 0) return; while(x) { ans[cnt++] = P[x]; x -= P[x]; } sort(ans, ans+cnt, cmp); cout << ans[0]; for(int i = 1; i < cnt; i++) cout << " " << ans[i];}int main(){ init(); for(int i = 0; i <= Q; i++) F[i]=~0U >> 3; F[0] = 0; G[0] = true; if(DP(Q) > 10000) cout<< 0 << endl; else { cout << DP(Q) << endl; print(Q); } return 0;}