质数中的质数（质数筛法

迈不过友情╰ 2022-06-11 05:44 198阅读 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 条评论，198人围观）

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

相关阅读

相关筛法求质数

筛法求质数给定一个正整数 n，请你求出 1∼n 中质数的个数。输入格式共一行，包含整数 n。输出格式共一行，包含一个整数，表示 1∼n 中质数的个数

Myth丶恋晨/ 2024年03月31日 13:50/ 0 赞/ 103 阅读

相关质数 AcWing 868. 筛质数线性筛

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

水深无声/ 2023年09月28日 11:35/ 0 赞/ 30 阅读

相关质数 AcWing 868. 筛质数

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

川长思鸟来/ 2023年09月28日 11:34/ 0 赞/ 23 阅读

相关质数 AcWing 868. 筛质数

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

旧城等待，/ 2023年09月28日 11:34/ 0 赞/ 41 阅读

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

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

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

相关质数的筛法

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

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

相关质数中的质数

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

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

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

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

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

相关数论——质数筛法

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

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

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

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

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