素数距离问题

╰+攻爆jí腚メ 2022-06-13 12:28 170阅读 0赞

## 素数距离问题 ##

时间限制： 3000 ms  |  内存限制： 65535 KB

难度： 2

描述

现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。  
如果输入的整数本身就是素数，则输出该素数本身，距离输出0

输入

第一行给出测试数据组数N(0<N<=10000)  
接下来的N行每行有一个整数M(0<M<1000000)，

输出

每行输出两个整数 A B.  
其中A表示离相应测试数据最近的素数，B表示其间的距离。

样例输入

3
    6
    8
    10

样例输出

5 1
    7 1
    11 1

#include <bits/stdc++.h>
    using namespace std;
    #define N 1000010
    bool prime[N];
    int main()
    {
        int i,j,t,n,b,a;
        prime[2]=true;//筛选法求素数
        for(i=3;i<N;i++)
        {
            if(i%2)
                prime[i]=true;
        else
            prime[i]=false;
        }
        for(i=3;i<=sqrt(N);i++)
            {
                if(prime[i])
                for(j=i+i;j<N;j=j+i)
                prime[j]=false;
            }
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            i=n;
            while(1)
            {
                if(prime[i])//左方向
                {
                    a=n-i;
                    break;
                }
                i--;
            }
            j=n;
            while(1)
            {
                if(prime[j])//右方向
                {
                    b=j-n;
                    break;
                }
                j++;
            }
            if(b<a)
                printf("%d %d\n",j,b);
            else
                printf("%d %d\n",i,a);
        }
        return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关题目24 素数距离问题

![20160728113355379][] 已AC代码： include<cstdio> include<cmath> int isPrime(i

￡神魔★判官ぃ/ 2022年09月24日 08:30/ 0 赞/ 115 阅读

相关 NYOJ 24 素数距离问题

素数距离问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输

比眉伴天荒/ 2022年08月25日 01:49/ 0 赞/ 130 阅读

相关南阳题目24-素数距离问题

素数距离问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输

缺乏、安全感/ 2022年08月20日 09:13/ 0 赞/ 152 阅读

相关素数距离问题(nyoj24)

素数距离问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，

墨蓝/ 2022年08月08日 12:53/ 0 赞/ 136 阅读

相关素数距离问题

素数距离问题时间限制： 3000 ms | 内存限制： 65535 KB 难度： 2 描述现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，

╰+攻爆jí腚メ/ 2022年06月13日 12:28/ 0 赞/ 171 阅读

相关素数距离-南阳online_judge语言入门

![这里写图片描述][SouthEast] include<stdio.h> include<math.h> int main(){

妖狐艹你老母/ 2022年06月01日 04:57/ 0 赞/ 129 阅读

相关素数问题

素数又称为质数即除了1和本身，不能够被其他数整除.1不是素数。判断一个数n是否为素数，只需要判断n是否能够被2和![b03533fa828ba61e582843574234

柔光的暖阳◎/ 2022年05月19日 09:26/ 0 赞/ 241 阅读

相关 acm 素数距离问题

素数距离问题时间限制：3000 ms | 内存限制：65535 KB 难度：2 输入第一行给出测试数据组数N(0<N<=10000) 接下来的N行每行有

缺乏、安全感/ 2022年05月18日 02:06/ 0 赞/ 331 阅读

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

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

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

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