悼念512汶川大地震遇难同胞——来生一起走(dfs+打表)

作者: 战神_私人司机
来源: 51数据库
2021-09-02

题意：5可以有两种 2 3， 5.质数之和
因为23 32是重复的
由于数据小，如果数据小于100，连打表都不用

#include<bits/stdc++.h>
using namespace std;
int t, n, m;
int dp[100], step, cnt;
int judge(int u){
    for(int i = 2; i <= sqrt(u); i ++)
        if(u%i==0)return 0;
    return 1;
}
void init(){
    for(int i = 2; i <= 150; i ++){
        if(judge(i))
            dp[++step] = i;
    }
}
void dfs(int ans, int n, int k){
    if(ans > n)return ;
    if(ans == n){
        cnt ++;
        return ;
    }
    for(int i = k; i <= step; i ++){
        dfs(ans+dp[i],n, i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    init();
    cin >> t;
    while(t --){
        cin >> n;
        cnt = 0;
        dfs(0, n, 1);
        cout << cnt << endl; 
    }
    return 0;
}