116. 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
2
3 3
用时:14min
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxnum=10001;
bool isntprime[maxnum];//是否质数
bool supp[maxnum];//是否superprime
int sup[300],pind;//把superprime放在一起
int ans[maxnum][2];//每个数必然=一个放在queue里的数+一个superprime,相当于记录路径
int vis[maxnum];//bfs记录状态
int n;
queue<int>que;
int bfs(){//找出当前数由那些超级质数构成,可以
while(!que.empty()&&vis[n]==0){
int tp=que.front();que.pop();
for(int i=0;i<pind;i++){
if(tp+sup[i]<=n&&vis[tp+sup[i]]==0){
vis[tp+sup[i]]=vis[tp]+1;
ans[tp+sup[i]][0]=sup[i];
ans[tp+sup[i]][1]=tp;
que.push(tp+sup[i]);
if(tp+sup[i]==n)break;
}
else if(tp+sup[i]>n)break;
}
}
return vis[n];
}void calc(){//找出超级质数
int cnt=1;
for(int i=3;i<maxnum;i+=2){
if(!isntprime[i]){
cnt++;
if(((cnt&1)!=0||cnt==2)&&!isntprime[cnt]){
sup[pind++]=i;
supp[i]=true;
vis[i]=1;
if(i<=n)que.push(i);
}
for(int j=3*i;j<maxnum;j+=2*i){
isntprime[j]=true;
}
}
}
}int main(){
scanf("%d",&n);
calc();
int num=bfs();
if(num==0){
puts("0");
}
else {
printf("%d\n",vis[n]);
int tn=n;
while(!supp[tn]){
printf("%d ",ans[tn][0]);
tn=ans[tn][1];
}
printf("%d\n",tn);
}
return 0;
}