HDU 4715 Difference Between Primes (打表)

Difference Between Primes

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 860 Accepted Submission(s): 278

Problem Description

All you know Goldbach conjecture.That is to say, Every even integer greater than 2 can be expressed as the sum of two primes. Today, skywind present a new conjecture: every even integer can be expressed as the difference of two primes. To validate this conjecture, you are asked to write a program.

Input

The first line of input is a number nidentified the count of test cases(n<10^5). There is a even number xat the next nlines. The absolute value of xis not greater than 10^6.

Output

For each number xtested, outputstwo primes aand bat one line separatedwith one space where a-b=x. If more than one group can meet it, output the minimum group. If no primes can satisfy it, output 'FAIL'.

Sample Input

3
6
10
20

Sample Output

11 5
13 3
23 3

Source

2013 ACM/ICPC Asia Regional Online —— Warmup

思路 ： 打表

总结： 不要忘了有负数的情况，

使用 Scanner sc = new Scanner(new BufferedInputStream(System.in)); 和

System.out.println(); 程序执行时间如下图

使用： BufferedReader bu=new BufferedReader(new InputStreamReader(System.in)); 和

PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out),true); 程序如下图

import java.io.*;
import java.util.*;
public class Main {
	int max=(int)Math.pow(10, 6)+10;
	boolean a[]=new boolean[max];
	public static void main(String[] args) throws IOException{
		new Main().work();
	}
	void work() throws IOException{
		BufferedReader bu=new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out),true);
		isPrime();
		int n=Integer.parseInt(bu.readLine());
		while(n--!=0){
			int x=Integer.parseInt(bu.readLine());
			int m=x>0?x:Math.abs(x);
			boolean boo=true;
			int i=2;
			for(;i<max;i++){
				if(a[i+m]&&a[i]){
					boo=false;
					break;
				}
			}
			if(!boo){
				if(x>0)
					pw.println((i+m)+" "+i);
				else
					pw.println(i+" "+(i+m));
			}
			else
				pw.println("FAIL");
		}
	}
	//素数表
	void isPrime(){
		Arrays.fill(a,true);
		for(int i=2;i<max;i++){
			if(a[i]){
				for(int j=2*i;j<max;j+=i){
					a[j]=false;
				}
			}
		}
	}
}