14418: 找素数

14418: 找素数

时间限制: 1 Sec   内存限制: 128 MB

题目描述

素数又称质数，是指一个大于 1 的正整数，如果除了 1 和它本身以外，不能再被其它的数整除， 例如：2、3、5、97 等都是素数。2 是最小的素数。
现在，给你 n 个数字，请你从中选取一部分，用它们拼出一个最大的素数。
注意：某个数字出现多少次你就可以用多少次，6 与 9 不能混用。

输入

输入共 2 行：
第 1 行，1 个整数 n，表示所给你的数字的个数。
第 2 行，n 个数字，用一个空格隔开，其含义如题目所述。

输出

输出共 1 行，1 个整数，为找到的最大素数。若无法拼出素数，输出-1。

样例输入 Copy

3 2 7 9

样例输出 Copy

97

提示

对于 30%的数据：n ≤ 3；
对于 60%的数据：n ≤ 4；
对于 100%的数据：n ≤ 5。

解析：比起判断质数，我认为这道题更复杂的地方在于搜索部分，因此把他划分在搜索算法这块。直接一个个数字从大到小一位一位搜索过来。如果是质数就输出答案。

由于本题数据量不大，不需要线性筛。

#include<bits/stdc++.h>

using namespace std;

long long now;

int a[8],n;

bool b[8];

bool t;

long long ans=0;

void dfs(int no){

if(no>n){

t=0;

for(long long i=2;i*i<=now;i++)

if(now%i==0){t=1;break;}

if(now<=1) t=1;

if(!t) ans=max(ans,now);

return;

}

//if(!t) return;

for(int i=n;i>=1;i--)

// if(!t) return;

if(!b[i]){

b[i]=1;now=now*10+a[i];dfs(no+1);

now/=10;b[i]=0;//if(!t) return;

}

dfs(no+1);

}

int main(){

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

t=1;sort(a+1,a+1+n);now=0;

memset(b,0,sizeof(b));

dfs(1);

if(ans==0) printf("-1\n");

else printf("%lld\n",ans);

return 0;

}