题意:给出n,输出n位超级质数,超级质数的定义为“依次去掉右边一位后仍然为质数的数”
因为一个n位质数去掉右边一位数之后仍然为质数,说明它是由n-1位超级质数演变而来的,
同理,n-1位超级质数也由n-2位超级质数演变而来- - -- - 所以按照位数从第一位广搜到n位即可
注意的地方是判重,最开始用的是一个vis[]数组,可是因为位数有8位,mle了 后来又想把每个数分成两半,比如73939133,可以这样判断vis[7393][9133]是否为1,= =后来发现这样用的内存貌似更多= =
最后用set就可以了,把搜到的符合题意的都放进去set里面,再输出set里面的元素就可以了,因为set里面的元素不重复
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<set> 7 #include<vector> 8 #include<map> 9 10 #include<queue> 11 #include<algorithm> 12 #define mod=1e9+7; 13 using namespace std; 14 15 typedef long long LL; 16 int n; 17 set<int> p; 18 19 20 21 int prime(int n){ 22 if(n<2) return 0; 23 for(int i=2;i<=sqrt(double(n));i++) 24 if(n%i==0) return 0; 25 return 1; 26 } 27 28 29 void bfs(){ 30 int head,next; 31 queue<int>q; 32 q.push(0); 33 int tmp=0; 34 35 while(tmp++<n){ 36 int size=q.size(); 37 while(size--){ 38 head=q.front();q.pop(); 39 if(n==1) p.insert(2); 40 if(tmp==1&&n!=1) q.push(2); 41 42 for(int i=0;i<=9;i++){ 43 next=head*10+i; 44 if(prime(next)){ 45 if(tmp==n) p.insert(next); 46 else q.push(next); 47 } 48 } 49 } 50 } 51 } 52 int main(){ 53 while(scanf("%d",&n)!=EOF){ 54 p.clear(); 55 bfs(); 56 for(set<int>::iterator it=p.begin();it!=p.end();++it) 57 cout<<*it<<" "; 58 } 59 return 0; 60 }
另外还有一个地方就是(因为是看的一个pdf上的),在判断队列的时候,用size=q.size();while(size--)来判断队列是否为空
自己写的时候,写的是while(!q.empty()),后来发现这样会陷入死循环,当n>=2时,队列里面始终有2= =还木有改出来