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

￡神魔★判官ぃ 2022-06-14 04:39 180阅读 0赞

Think:  
1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作  
2方法：输入数据范围为【0,1299709】发现可用下标表示，直接用筛法建立素数表然后进行查询即可

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int v[1400000];
    
    void Init();
    
    int main(){
        Init();
        int t, k, a, b;
        while(scanf("%d", &t) && t){
    
            if(!v[t])
                printf("0\n");
            else {
    
                k = t;
                while(v[k]){
                    k--;
                    if(!v[k]){
                        a = k;
                        break;
                    }
                }
    
                k = t;
                while(v[k]){
                    k++;
                    if(!v[k]){
                        b = k;
                        break;
                    }
                }
    
                printf("%d\n", b-a);
            }
        }
        return 0;
    }
    void Init(){
        memset(v, 0, sizeof(v));
        v[1] = 1, v[2] = 0;
        for(int i = 2; i <= 1400000; i++){
            if(!v[i]){
                for(int j = i*2; j <= 1400000; j += i){
                    v[j] = 1;
                }
            }
        }
    }

[vjudge]: https://vjudge.net/problem/UVA-1644

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 83 阅读

相关 UVA 524 素数环Prime Ring Problem (回溯法)

啃爹的输出格式！PE了好几次！ include<cstdio> include<cstring> include<cmath> using n

太过爱你忘了你带给我的痛/ 2024年02月17日 19:03/ 0 赞/ 69 阅读

相关 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 赞/ 39 阅读

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 212 阅读

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

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

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

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

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

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

相关 UVA - 10924 - Prime Words (素数)

输入一个由大小写字母组成的字符串，每个字符代表着不同的数字，计算出这个字符串的数值，判断是否是素数；首先我们打个素数表；然后利用ascll码存入数组中，然后判断就o

r囧r小猫/ 2022年06月07日 00:23/ 0 赞/ 168 阅读

相关 UVA - 10789 - Prime Frequency（素数打表）

题意是给出0-9，A-Z，a-z，组成的字符串，如果字符的个数是素数就输出这个字符。例如ABCC中的C的个数是素数，那么输出C；首先素数打表，剩下的就是如何储存每个

浅浅的花香味﹌/ 2022年06月07日 00:21/ 0 赞/ 217 阅读

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 285 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 287 阅读