acm练习：求最近的素数

小灰灰 2022-06-10 06:55 171阅读 0赞

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

## 描述 ##

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

## 输入 ##

第一行给出测试数据组数N(0

## 输出 ##

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

## 样例输入 ##

3  
6  
8  
10

## 样例输出 ##

5 1  
7 1  
11 1

## 我的代码： ##

#include<stdio.h>
    #define abs(a,b) (a>b?(a-b):(b-a))
    #define M 1000100
    int a[M],b[M];
    int main() {
        //初始化，算出Ｍ以内所有质数
        long int n,m,i,j,k;
        for(i=0;i<M;i++) b[i]=1;
        b[0]=0,b[1]=0;
        for(i=2;i<M;) {
            for(j=i,k=i*j;k<M;) {
                if(b[k]==1) b[k]=0;
                j++;
                k=j*i;
            }
            while(!b[++i]&&i<M);
        }
        for(i=0,j=0;i<M;i++) if(b[i]==1) a[j++]=i;
        //开始接收数据,逐个判断
        scanf("%ld",&n);
        for(i=0;i<n;i++) {
            scanf("%ld",&m);
            for(j=0,k=M;abs(a[j],m)<k;j++) {
                k=abs(a[j],m);
            }
            printf("%d %ld\n",a[j-1],k);
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 ACM.素数筛

一.埃氏筛筛法的思想是去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数都为合数。合数的倍数一定会在

清疚/ 2023年07月05日 11:57/ 0 赞/ 4 阅读

相关求素数

求素数 Time Limit: 100ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述求小于n的所有素数的数量。输入

た入场券/ 2022年08月10日 04:58/ 0 赞/ 177 阅读

相关 acm练习：求最近的素数

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

小灰灰/ 2022年06月10日 06:55/ 0 赞/ 172 阅读

相关 acm练习：素数求和问题

时间限制：3000 ms | 内存限制：65535 KB 难度：2 描述现在给你N个数（0 输入第一行给出整数M(0 输出每组测试数据结果占一

àì夳堔傛蜴生んèń/ 2022年06月10日 06:55/ 0 赞/ 182 阅读

相关 acm 素数

素数时间限制：3000 ms | 内存限制：65535 KB 难度：1 输入第一行：N 要竞猜的整数个数接下来有N行，每行有一个正整数X 1<=N

谁践踏了优雅/ 2022年05月18日 07:51/ 0 赞/ 204 阅读

相关 acm 素数距离问题

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

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

相关 python小练习----利用filter求素数

计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：首先，列出从2开始的所有自然数，构造一个序列： 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 1

左手的ㄟ右手/ 2022年02月21日 10:05/ 0 赞/ 254 阅读

相关求素数——多线程练习

编写一个有两个线程的程序，第一个线程用来计算2～100000之间的素数的个数，第二个线程用来计算100000～200000之间的素数的个数，最后输出结果。代码实现：

系统管理员/ 2021年12月24日 10:53/ 0 赞/ 211 阅读

相关求素数

\include<stdio.h> \include<math.h> int prime(int m); int main(void) \{ int co

傷城~/ 2021年11月09日 23:46/ 0 赞/ 319 阅读

相关求素数

素数：在大于1的整数中，只能被1和这个数本身整除的数，如2、3、5、7、11。也叫质数。求0-n之间所有的素数。测试用例：20

╰+哭是因爲堅強的太久メ/ 2021年09月15日 05:02/ 0 赞/ 383 阅读