素数距离问题

描述

现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出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 <stdio.h>
#include <string.h>
#define N 1000010 //此题的关键在于你素数标记数组要开大一些，保证往上找素数的时候可以找到需要的素数 

int flag[N];

int main(){
    int i;
    int j;
    int T;
    int number;
    int temp;
    
    int result;
    int distance;
    
    memset(flag,0,sizeof(int)*N);
    flag[0]=1;
    flag[1]=1;
    
    for(i=2;i*i<N;i++){
        if(flag[i]==0){
            for(j=i*i;j<N;j+=i){
                flag[j]=1;
            } 
        }
    }
    
    scanf("%d",&T);
    
    while(T--){
        scanf("%d",&number);
        
        temp=number;
        while(1){
            if(flag[temp]==0){
                result=temp;
                distance=number-temp;
                break;
            }
            temp--;
        }
        
        temp=number;
        while(1){
            if(flag[temp]==0){
                if(temp-number<distance){
                    distance=temp-number;
                    result=temp;
                }
                break;
            }
            temp++;
        }
        
        printf("%d %d
",result,distance); 
    }
    
    
    
    
    return 0;
}