搬自洛谷的一道题，可能起一个防AK的作用，虽然可能没起到就是了。

#include<cstdio>
#include<cstring>
using namespace std;
int dp[10001][10][10],a[1000],p[1000],r[100],t[10][10][10],cnt=0,cnt2=0,i,c,d,e,j,ans,n;
void premanage()
{
    memset(a,0,sizeof(a));
    memset(p,0,sizeof(p));
    memset(r,0,sizeof(r));
    memset(t,0,sizeof(t));
    memset(dp,0,sizeof(dp));
    for(i=2;i<1000;i++)
    {
        if(!a[i])
        {
            if(i<100)p[++cnt]=i;
            else
            {
                c=i/10%10;d=i%10;e=i/100;
                dp[3][c][d]++;
                if(!t[c][d][0])r[++cnt2]=i%100;
                t[c][d][0]++;
                t[c][d][t[c][d][0]]=e;
            }
        }
        for(j=1;j<=cnt&&i*p[j]<1000;j++)a[i*p[j]]=1;
    }
}
int dpp(int n,int c,int d)
{
    int i;
    if(n<3)return 0;
    if(!dp[n][c][d])for(i=1;i<=t[c][d][0];i++)dp[n][c][d]=(dp[n][c][d]+dpp(n-1,t[c][d][i],c))%1000000009;
    return dp[n][c][d];
}
void solve()
{
for(i=1;i<=cnt2;i++)ans=(ans+dpp(n,r[i]/10,r[i]%10))%1000000009;
}
int main()
{
    scanf("%d",&n);
    premanage();
    solve();
    printf("%d",ans);
    return 0;    
}

贴一个大佬的代码，大家也可以移步洛谷该题,实际是一道dp,有需要的大佬可以提前了解，已经掌握的大佬请无视蒟蒻颤抖。