质数中的质数（质数筛法

迈不过友情╰ 2022-06-11 05:44 144阅读 0赞

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数是多少（可以考虑用质数筛法来做）。

Input

输入一个数N(N <= 10^6)

Output

输出>=N的最小的质数中的质数。

Sample Input

20

Sample Output

31

#include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    bool vis[1000001];
    int a[10000];
    void A()
    {
        vis[2]=true;
        for(int i=3; i<=1000001; i+=2)
            vis[i]=true;
        for(int i=3; i<=sqrt(1000001); i+=2)
        {
            if(vis[i])
            {
                for(int j=i*i; j<=1000001; j+=i*2)
                    vis[j]=false;
            }
        }
    }
    int main()
    {
        int n,k=0,l=0;
        A();
        for(int i=1; i<=1000001; i++)
            if(vis[i])
            {
                k++;
                if(vis[k])
                {
                    a[l]=i;
                    l++;
                }
            }
        scanf("%d",&n);
        int b=lower_bound(a,a+l,n)-a;
        printf("%d\n",a[b]);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关【离线+筛法+MEX】阿宁的质数

一道蓝桥杯难度的题 [D-阿宁的质数\_牛客小白月赛56 (nowcoder.com)][D-_56 _nowcoder.com] 题意： ![09d1fffe18894

电玩女神/ 2024年03月16日 19:45/ 0 赞/ 30 阅读

相关关于质数的判定与快速筛法

一. 关于质数： 1.质数和合数是针对所有大于1的 “自然数” 来定义的(所有小于等于1的数都不是质数). 2.所有小于等于1的整数既不是质数也不是合数. 3.质数和

男娘i/ 2023年09月24日 14:26/ 0 赞/ 9 阅读

相关质数的筛法

上一篇博客：[LeetCode 1006. 笨阶乘——每日一题][LeetCode 1006.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Acce

绝地灬酷狼/ 2022年11月15日 15:49/ 0 赞/ 160 阅读

相关求质数

质数的定义：在除了1以外的自然数中，如果这个数在1和本身外没有别的因数，他就是质数。那我们来求解100以内的质数思路：定义里说的没有别的因数，

冷不防/ 2022年09月30日 13:56/ 0 赞/ 151 阅读

相关质数中的质数

质数中的质数 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述如果一个质数，它在质数

系统管理员/ 2022年08月14日 05:50/ 0 赞/ 142 阅读

相关质数中的质数（质数筛法

如果一个质数，在质数列表中的编号也是质数，那么就称之为质数中的质数。例如：3 5分别是排第2和第3的质数，所以他们是质数中的质数。现在给出一个数N，求>=N的最小的质数中的质数

迈不过友情╰/ 2022年06月11日 05:44/ 0 赞/ 145 阅读

相关质数因子

功能:输入一个正整数，按照从小到大的顺序输出它的所有质数的因子（如180的质数因子为2 2 3 3 5 ）最后一个数后面也要有空格详细描述：函数接口说明： p

谁践踏了优雅/ 2022年06月04日 09:11/ 0 赞/ 176 阅读

相关计数质数

题目描述统计所有小于非负整数 n 的质数的数量。示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2,

我会带着你远行/ 2022年02月25日 06:10/ 0 赞/ 215 阅读

相关数论——质数筛法

一、埃拉托斯特尼（Eratosthenes）筛法算法思想：　　要得到自然数n以内的全部素数，必须把不大于![5ab5c9ea15ce36d3884f4f0b39f33a

小灰灰/ 2021年11月10日 02:04/ 0 赞/ 411 阅读

相关 196. 质数距离(素数筛)

题目链接:https://www.acwing.com/problem/content/description/198/ [![知识共享许可协议][80x15.png]][

╰半夏微凉°/ 2021年10月29日 09:26/ 0 赞/ 341 阅读