编辑代码

#include <iostream>
using namespace std;

int n,ans;
int a[20];

bool check(int x)
{
    if(x <= 100)    return false;
    
    for(int i = 2;i * i <= x;i++)
    {
        if(x % i == 0)  return 0;
    }
    return true;
}

void dfs(int step = 1,int cnt = 0)
{
    if(step > n)
    {
        ans++;
        return;
    }

    if(step == 1)
    {
        a[step] = 0;
        if(step == 1 || step == 2 || check(a[step - 2] * 100 + a[step - 1] * 10 + a[step] * 1) )
            dfs(step + 1,cnt + 1);

    }
    for(int i = 1;i <= 9;i++)
    {
        a[step] = i;
        if(step == 1 || step == 2 || check(a[step - 2] * 100 + a[step - 1] * 10 + a[step] * 1) )
            dfs(step + 1,cnt + 1);
        else
            continue;
    }
}

int main() {
    cin>>n;
    dfs();
    cout<<ans;
    
	return 0;
}