大神求解(暴力会超时,别用指针啦,尽量优化算法)
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:综合作业 时间:2024/08/18 15:28:58
大神求解(暴力会超时,别用指针啦,尽量优化算法)
Description
设一个m位素数p由高到低每一位分别是a1,a2,...,am.定义一个素数是完全素数当且仅当对于任意k(1
Description
设一个m位素数p由高到低每一位分别是a1,a2,...,am.定义一个素数是完全素数当且仅当对于任意k(1
![大神求解(暴力会超时,别用指针啦,尽量优化算法)](/uploads/image/z/3193388-44-8.jpg?t=%E5%A4%A7%E7%A5%9E%E6%B1%82%E8%A7%A3%EF%BC%88%E6%9A%B4%E5%8A%9B%E4%BC%9A%E8%B6%85%E6%97%B6%2C%E5%88%AB%E7%94%A8%E6%8C%87%E9%92%88%E5%95%A6%2C%E5%B0%BD%E9%87%8F%E4%BC%98%E5%8C%96%E7%AE%97%E6%B3%95%EF%BC%89)
这是AC的代码哈.我在你的另一个问题里也回答了.
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
int ans[100]={
\x05\x052,
\x05\x053,
\x05\x055,
\x05\x057,
\x05\x0523,
\x05\x0529,
\x05\x0531,
\x05\x0537,
\x05\x0553,
\x05\x0559,
\x05\x0571,
\x05\x0573,
\x05\x0579,
\x05\x05233,
\x05\x05239,
\x05\x05293,
\x05\x05311,
\x05\x05313,
\x05\x05317,
\x05\x05373,
\x05\x05379,
\x05\x05593,
\x05\x05599,
\x05\x05719,
\x05\x05733,
\x05\x05739,
\x05\x05797,
\x05\x052333,
\x05\x052339,
\x05\x052393,
\x05\x052399,
\x05\x052939,
\x05\x053119,
\x05\x053137,
\x05\x053733,
\x05\x053739,
\x05\x053793,
\x05\x053797,
\x05\x055939,
\x05\x057193,
\x05\x057331,
\x05\x057333,
\x05\x057393,
\x05\x0523333,
\x05\x0523339,
\x05\x0523399,
\x05\x0523993,
\x05\x0529399,
\x05\x0531193,
\x05\x0531379,
\x05\x0537337,
\x05\x0537339,
\x05\x0537397,
\x05\x0559393,
\x05\x0559399,
\x05\x0571933,
\x05\x0573331,
\x05\x0573939,
\x05\x05233993,
\x05\x05239933,
\x05\x05293999,
\x05\x05373379,
\x05\x05373393,
\x05\x05593933,
\x05\x05593993,
\x05\x05719333,
\x05\x05739391,
\x05\x05739393,
\x05\x05739397,
\x05\x05739399,
\x05\x052339933,
\x05\x052399333,
\x05\x052939999,
\x05\x053733799,
\x05\x055939333,
\x05\x057393913,
\x05\x057393931,
\x05\x057393933,
\x05\x0523399339,
\x05\x0529399999,
\x05\x0537337999,
\x05\x0559393339,
\x05\x0573939133
};
int main(){
\x05int i,n;
\x05while(scanf("%d",&n)!=EOF){
\x05\x05int weiShu=int(pow(10,n-1));
\x05\x05for(i=0;i<83;i++)
\x05\x05\x05if(ans[i]/weiShu>=1 && ans[i]/weiShu<10)
\x05\x05\x05\x05printf("%d\n",ans[i]);
\x05}
\x05return 0;
}
再问: 大神能不能帮我写一个递归的呢?比如2位数满足条件的又23,那么3位数就只要判断231 233 237 239就行了,这个会超时吗?我写一下午都还没弄出来。。。。。。。
再答: #include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
int prm[6]={1,2,3,5,7,9};
int isPrime(long n){
int i;
if (n < 2) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
int tmp=sqrt(n);
for (i = 3; i <= tmp; i += 2)
if (n % i == 0) return 0;
return 1;
}
int ans[100],ansCnt=0;
void dfs(int n){
int i,tmp;
if(isPrime(n)){
ans[ansCnt++]=n;
for(i=0;i<5;i++){
tmp=n*10+2*i+1;
if(tmp>=100000000)
return;
dfs(tmp);
}
}
}
int main(){
int i,n;
for(i=0;i<6;i++)
dfs(prm[i]);
sort(ans,ans+ansCnt);
while(scanf("%d",&n)!=EOF){
int weiShu=int(pow(10,n-1));
for(i=0;i<ansCnt;i++)
if(ans[i]/weiShu>=1 && ans[i]/weiShu<10)
printf("%d\n",ans[i]);
}
return 0;
}参考这个递归的代码哈。
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
int ans[100]={
\x05\x052,
\x05\x053,
\x05\x055,
\x05\x057,
\x05\x0523,
\x05\x0529,
\x05\x0531,
\x05\x0537,
\x05\x0553,
\x05\x0559,
\x05\x0571,
\x05\x0573,
\x05\x0579,
\x05\x05233,
\x05\x05239,
\x05\x05293,
\x05\x05311,
\x05\x05313,
\x05\x05317,
\x05\x05373,
\x05\x05379,
\x05\x05593,
\x05\x05599,
\x05\x05719,
\x05\x05733,
\x05\x05739,
\x05\x05797,
\x05\x052333,
\x05\x052339,
\x05\x052393,
\x05\x052399,
\x05\x052939,
\x05\x053119,
\x05\x053137,
\x05\x053733,
\x05\x053739,
\x05\x053793,
\x05\x053797,
\x05\x055939,
\x05\x057193,
\x05\x057331,
\x05\x057333,
\x05\x057393,
\x05\x0523333,
\x05\x0523339,
\x05\x0523399,
\x05\x0523993,
\x05\x0529399,
\x05\x0531193,
\x05\x0531379,
\x05\x0537337,
\x05\x0537339,
\x05\x0537397,
\x05\x0559393,
\x05\x0559399,
\x05\x0571933,
\x05\x0573331,
\x05\x0573939,
\x05\x05233993,
\x05\x05239933,
\x05\x05293999,
\x05\x05373379,
\x05\x05373393,
\x05\x05593933,
\x05\x05593993,
\x05\x05719333,
\x05\x05739391,
\x05\x05739393,
\x05\x05739397,
\x05\x05739399,
\x05\x052339933,
\x05\x052399333,
\x05\x052939999,
\x05\x053733799,
\x05\x055939333,
\x05\x057393913,
\x05\x057393931,
\x05\x057393933,
\x05\x0523399339,
\x05\x0529399999,
\x05\x0537337999,
\x05\x0559393339,
\x05\x0573939133
};
int main(){
\x05int i,n;
\x05while(scanf("%d",&n)!=EOF){
\x05\x05int weiShu=int(pow(10,n-1));
\x05\x05for(i=0;i<83;i++)
\x05\x05\x05if(ans[i]/weiShu>=1 && ans[i]/weiShu<10)
\x05\x05\x05\x05printf("%d\n",ans[i]);
\x05}
\x05return 0;
}
再问: 大神能不能帮我写一个递归的呢?比如2位数满足条件的又23,那么3位数就只要判断231 233 237 239就行了,这个会超时吗?我写一下午都还没弄出来。。。。。。。
再答: #include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cstring>
#include<math.h>
#include<stdio.h>
#include<map>
#include<set>
using namespace std;
int prm[6]={1,2,3,5,7,9};
int isPrime(long n){
int i;
if (n < 2) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
int tmp=sqrt(n);
for (i = 3; i <= tmp; i += 2)
if (n % i == 0) return 0;
return 1;
}
int ans[100],ansCnt=0;
void dfs(int n){
int i,tmp;
if(isPrime(n)){
ans[ansCnt++]=n;
for(i=0;i<5;i++){
tmp=n*10+2*i+1;
if(tmp>=100000000)
return;
dfs(tmp);
}
}
}
int main(){
int i,n;
for(i=0;i<6;i++)
dfs(prm[i]);
sort(ans,ans+ansCnt);
while(scanf("%d",&n)!=EOF){
int weiShu=int(pow(10,n-1));
for(i=0;i<ansCnt;i++)
if(ans[i]/weiShu>=1 && ans[i]/weiShu<10)
printf("%d\n",ans[i]);
}
return 0;
}参考这个递归的代码哈。