首页 > 代码库 > Java用筛子法求素数

Java用筛子法求素数

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

 
输入
第一行给出测试数据组数N(0<N<=10000)
接下来的N行每行有一个整数M(0<M<1000000),
输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数,B表示其间的距离。
样例输入
36810
样例输出
5 17 111 1

 1 import java.util.Scanner; 2  3 public class Main { 4     public static void main(String[] args) { 5         int T; 6         Scanner scanner=new Scanner(System.in); 7         int number; 8         int result; 9         int distance;10         int temp;11         int N=1000010;12         int flag[]=new int[N];13         int i;14         int j;15         16         for(i=0;i<N;i++)17             flag[i]=0;18         19         flag[0]=1;20         flag[1]=1;21         22         for(i=2;i*i<N;i++){23             if(flag[i]==0){24                 for(j=i*i;j<N;j+=i)25                     flag[j]=1;26             }27         }28         29         T=scanner.nextInt();30         while(true){31             if(T==0)32                 break;33             T--;34             35             number=scanner.nextInt();36             37             if(number==1){38                 System.out.println("2 1");39                 continue;40             }41             42             temp=number;43             while(true){44                 if(flag[temp]==0){45                     result=temp;46                     distance=number-temp;47                     break;48                 }49                 temp--;50             }51             52             temp=number;53             while(true){54                 if(flag[temp]==0){55                     if(temp-number<distance){56                         result=temp;57                         distance=temp-number;58                     }59                     break;60                 }61                 temp++;62             }63             64             System.out.println(result+" "+distance);65         }66     }67 }

 

 

Java用筛子法求素数