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 ;

}