UVA - 10394 - Twin Primes（素数对）

电玩女神 2022-06-07 00:23 156阅读 0赞

定义了一个素数对的概念，就是如果p是素数的话，p+2也是素数的话，那么（p，p+2）就是一组素数对；  
那么我们在打素数表的时候，顺便判断i-2是否是素数即可；

#include<iostream>
    #include<cstring>
    #include<cmath>
    #define ll unsigned long long //数据太大，这个比long long还大
    #define MAXN 100010
    #define maxn 20000010
    using namespace std;
    
    bool vis[maxn];
    ll a[MAXN];//p
    ll b[MAXN];//p+2
    
    ll kase = 0;
    
    
    void checkprime(ll n) {
       //素数打表
        memset(vis, true, sizeof(vis));
        vis[0] = vis[1] = false;
        for(ll i = 2; i <= n; i++) {
            if(vis[i]) {
                if(vis[i-2]) {
                    ++kase;
                    a[kase] = i - 2;
                    b[kase] = i;
                }
                for(ll j = i*i; j <= n; j+=i) {
                    vis[j] = false;
                }
            }
            if(kase >= 100000) break;//如果个数够了就break，题目要求
        }
    }
    
    int main() {
        ll n;
        checkprime(maxn);
        while(~scanf("%lu", &n)) {
            printf("(%lu, %lu)\n", a[n], b[n]);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

相关 uva 10140——Prime Distance

题意：题目出的很简单，给定一个数据范围（好吧，又是给定一个范围），然后问你在这个给定的范围内，哪两个相邻素数挨的最近，哪两个最远。思路：这破题数据量很大，如果直接打

客官°小女子只卖身不卖艺/ 2022年08月09日 13:49/ 0 赞/ 20 阅读

相关 Sum of Consecutive Prime Numbers UVA - 1210——素数表+初级dp思想

Think: 1题意：输入正整数n(2 <= n <= 10000),求连续素数之和等于n的方案数 2思路： 1>筛法建立素数表+初级dp思想(从后往前规划得到当前

逃离我推掉我的手/ 2022年06月14日 04:49/ 0 赞/ 178 阅读

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

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

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

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

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

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

相关 UVA - 10394 - Twin Primes（素数对）

定义了一个素数对的概念，就是如果p是素数的话，p+2也是素数的话，那么（p，p+2）就是一组素数对；那么我们在打素数表的时候，顺便判断i-2是否是素数即可； i

电玩女神/ 2022年06月07日 00:23/ 0 赞/ 157 阅读

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

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

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

相关 UVA P12101 【Prime Path】

题库：UVA 题号：12101 题目：Prime Path link ：[https://www.luogu.org/problemnew/sho

素颜马尾好姑娘i/ 2021年12月03日 11:17/ 0 赞/ 198 阅读

相关 HDU - 3792- Twin Prime Conjecture【数论】题解

目录 1.题目 2.代码 1.题目 If we define dn as: dn = pn+1-pn, wh

末蓝、/ 2021年07月24日 17:10/ 0 赞/ 378 阅读