acm 素数距离问题

缺乏、安全感 2022-05-18 02:06 329阅读 0赞

## 素数距离问题 ##

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

难度：2

输入

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

输出

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

样例输入

3
    6
    8
    10

样例输出

5 1
    7 1
    11 1

描述

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

\#include<stdio.h>

int is\_prime\_num(int n)\{            //判断是否是素数  
   
 if(n == 1) return 0;            //如果是1，不是，返回0  
   
 for(int i = 2; i \* i <= n; i++)\{  
    
  if(n % i == 0) return 0;  
    
 \}  
   
 return 1;  
\}

int main()\{  
   
 int n,m,left,right,i,j;  
   
 scanf("%d",&n);  
   
 while(n--)\{  
    
  scanf("%d",&m);  
    
  if(is\_prime\_num(m))\{            //若本身是素数，输出去本身  
     
   printf("%d 0\\n",m);  
  \}  
    
  else \{  
     
     
   j =  i = m;  
     
   while(!is\_prime\_num(j)&& j != 0)\{       //向左查找  
    j--;  
   \}  
     
   while(!is\_prime\_num(i))\{         //向右查找  
    i++;  
   \}  
     
   left = m - j;  
     
   right = i - m;  
     
   if(j == 0) printf("%d %d\\n",i,right);      //向左没有找到，输出右方数据  
     
   else if(left <= right)\{  
      
    printf("%d %d\\n",j,left);  
      
   \}  
     
   else \{  
      
    printf("%d %d\\n",i,right);  
      
   \}  
     
  \}  
    
 \}  
   
 return 0;  
\}