POJ - 3518 - Prime Gap（筛素数）

桃扇骨 2022-06-08 11:20 156阅读 0赞

给出一个数字n，求n所在得一个区间的长度，区间是最近的两个素数为边界；

那么n如果为素数的话，那么直接输出0；

先打表，因为用的是前10万个素数，所以在打表的时候，记录素数的个数；

以n点为中心向两边判定，一定要先判定再加减；

#include<iostream>
    #include<cstring>
    #include<cmath>
    #define ll long long
    #define MAXN 10000005
    #define maxn 100005
    using namespace std;
    
    bool isprime[MAXN];
    ll num = 0;
    
    void checkprime() {
        memset(isprime, true, sizeof(isprime));
        num++;//因为2也是素数
        for(ll i = 2; num <= maxn; i++) {
            if(isprime[i]) {
                num++;//如果没有标记的话就是素数，标记个数
                for(ll j=i+i; j <= MAXN; j+=i) {
       //以i为倍数的数都是偶数，都不是素数，全部筛除
                    isprime[j] = false;
                }
            }
        }
    }
    
    int main () {
        int n;
        checkprime();
        while(cin >> n && n) {
            int ans = 1;
            if(isprime[n]) puts("0");
            else {
                int l = n-1, r = n;//预处理向左
                while(!isprime[l]) {
       //向左
                    l--;
                    ++ans;
                }
                while(!isprime[r]) {
       //向右
                    r++;
                    ++ans;
                }
                printf("%d\n", ans);
            }
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 2136 Largest prime factor（素数筛法）

Largest prime factor Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768

柔情只为你懂/ 2024年02月17日 19:44/ 0 赞/ 68 阅读

相关 POJ 3126 Prime Path(BFS + 素数判定)

题意：给定两个四位素数作为终点和起点，每次可以改变起点数的某一位，且改变后的数仍然是素数，如果变换成终点数字输出最短步数，否则输出Impossible。 includ

雨点打透心脏的1/2处/ 2024年02月17日 19:07/ 0 赞/ 73 阅读

相关 UVA - 1404 Prime k-tuple【筛素数】

discription \{p1, . . . , pk : p1 < p2 < . . . < pk\} is called a prime k-tuple of dis

缺乏、安全感/ 2023年07月04日 14:14/ 0 赞/ 21 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 38 阅读

相关 JAG Asia 2017 C-----Prime-Factor Prime(素数区间筛)

C: Prime-Factor Prime 时间限制: 1 Sec 内存限制: 128 MB 题目描述 A positive integer is called

Bertha 。/ 2023年06月05日 12:33/ 0 赞/ 31 阅读

相关 POJ 2689-Prime Distance(区间素数)

Prime Distance <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS<

向右看齐/ 2022年08月23日 00:37/ 0 赞/ 222 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 167 阅读

相关 POJ - 3518 - Prime Gap（筛素数）

给出一个数字n，求n所在得一个区间的长度，区间是最近的两个素数为边界；那么n如果为素数的话，那么直接输出0；先打表，因为用的是前10万个素数，所以在打表的时候，记录素数

桃扇骨/ 2022年06月08日 11:20/ 0 赞/ 157 阅读

相关 Prime Path POJ - 3126 (BFS,素数距离)

The ministers of the cabinet were quite upset by the message from the Chief of Security

拼搏现实的明天。/ 2022年04月24日 02:58/ 0 赞/ 195 阅读

相关 Prime Path素数筛与BFS动态规划

本文共2053个字，预计阅读时间需要6分钟。 BFS BFS，其英文全称是Breadth First Search。 BFS并不使用经验法则算法。从算法的观点，所有因为

朴灿烈づ我的快乐病毒、/ 2022年01月23日 03:37/ 0 赞/ 199 阅读