首页 > 代码库 > 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用筛子法求素数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。