首页 > 代码库 > 51NOD 1181 质数中的质数（质数筛法）
51NOD 1181 质数中的质数（质数筛法）
1181 质数中的质数（质数筛法）
如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。
Input
输入一个数N(N <= 10^6)Output
输出>=N的最小的质数中的质数。
自己写的模拟版本
#include <bits/stdc++.h>using namespace std;const int maxn = 1e7;bool s[maxn];bool p[maxn];int n;void solve (){ for(int i=1;i <= 1e6+10 ;i++) s[i] = 1; s[1] = 0; for(int i=2;i*i <= 1e6;i++){ if( s[i] ){ for(int j= i*i; j <= 1e6;j+=i ){ s[j] = 0; } } } int cnt = 1; for(int i=1;i <= 1e6;i++) p[i] = s[i]; for(int i=1;i <= 1e6;i++){ if(s[i]){ if(p[cnt] == 0) s[i] = 0; cnt++; } } /*for(int i=1;i <= 100;i++) printf("%d ",s[i]); printf("\n");*/}int main (){ scanf("%d",&n); solve(); for(int i=n;i<=1e6;i++){ if( s[i] ) { printf("%d\n",i); break; } } return 0;}
然后 网上搜索到一个比较好的方法
就是 把不是素数的都标记好
（注意以后素数打表的时候 还是要用long long 否则会爆int的
#include <bits/stdc++.h>using namespace std;const int maxn = 1e6+1000;typedef long long ll;bool s[maxn];int n;int main (){ //freopen("out.txt","w",stdout); scanf("%d",&n); int cnt = 1; s[1] = 1,s[2] = 0; for(ll i=2;i <= 1e6+500;i++) { if(!s[i]) { if(!s[cnt] && i >= n) { printf("%d\n",i); break; } cnt++; for(ll j=i*i;j <= 1e6;j+=i) { s[j] = 1; } } } return 0;}
51NOD 1181 质数中的质数（质数筛法）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。