Index of super-prime – SGU 116（素数+背包）

题目大意：素数表2,3,5,7,11…..如果一个素数所在的位置还是素数，那么这个素数就是超级素数，比如3在第2位置，那么3就是超级素数…..现在给你一个数，求出来这个数由最少的超级素数的和组成，输出这个超级素数。

分析：因为给的数字并不大，所以直接用完全背包求出来即可。

代码如下：

=================================================================================================================================

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int MAXN = ;
const int oo = 1e9+;int sup[MAXN], cnt;
int dp[MAXN];void superPrime()
{
    bool used[MAXN]={,};
    cnt = ;    for(int k=,i=; i<MAXN; i++)
    {
        if(!used[i])
        {
            k++;
            if(used[k] == )
                sup[++cnt] = i;
            for(int j=i+i; j<MAXN; j+=i)
                used[j] = true;
        }
    }
}int main()
{
    superPrime();    int N, from[MAXN];    scanf("%d", &N);    for(int i=; i<=N; i++)
        dp[i] = oo;    for(int i=; i<=cnt; i++)
    for(int j=sup[i]; j<=N; j++)
    {
        if(dp[j-sup[i]]+ < dp[j])
        {
            dp[j] = dp[j-sup[i]]+;
            from[j] = j-sup[i];
        }
    }    if(dp[N] == oo)
        printf("0\n");
    else
    {
        printf("%d\n", dp[N]);
        for(int i=N; i!=; i=from[i])
        {
            printf("%d%c", i-from[i], from[i]?' ':'\n');
        }
    }    return ;
}