题目描述

可行性剪枝：
第一位一定是 2，3，5，7中的一个 ，1不可以，1既不是质数，也不是合数。
剩下的位里，偶数不行，每步对5个奇数dfs。
排序，去重，输出。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int ans=0;
int n;
int prime[10] = {1,3,5,7,9};

vector<int> v;

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

void dfs(int pos,int x)
{
    if(!is_prime(x)) return ;

    if(pos == n)
    {
        v.push_back(x);
        return ;
    }
    else
    {
        for(int i=0;i<5;i++)
        {
            dfs(pos+1,x*10+prime[i]);
        }
    }
    return ;
}

int main()
{
    v.clear();
    scanf("%d",&n);

    dfs(1,2);
    dfs(1,3);
    dfs(1,5);
    dfs(1,7);

    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());


    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<endl;
    }

    return 0;
}