Aizu Online Judge 0150 Twin Prime

■0150 Twin Prime

やるだけ．

素数判定は簡単なものでもO(√n)で済むので，今回のケースでは予め全て求めておくことが可能．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  void run(){  
17.   boolean[] fs=new boolean[10001];  
18.   for(int i=0; i<10001; i++){  
19.    fs[i]=isPrime(i-2)&&isPrime(i);  
20.   }  
21.   
22.   for(; sc.hasNext();){  
23.    int n=sc.nextInt();  
24.    if(n==0){  
25.     break;  
26.    }  
27.    for(; !fs[n]; n--);  
28.    println((n-2)+" "+n);  
29.   }  
30.  }  
31.   
32.  boolean isPrime(int n){  
33.   for(int i=2; i*i<=n; i++){  
34.    if(n%i==0){  
35.     return false;  
36.    }  
37.   }  
38.   return n>=2;  
39.  }  
40.   
41.  void debug(Object... os){  
42.   System.err.println(Arrays.deepToString(os));  
43.  }  
44.   
45.  void print(String s){  
46.   System.out.print(s);  
47.  }  
48.   
49.  void println(String s){  
50.   System.out.println(s);  
51.  }  
52.   
53.  public static void main(String[] args){  
54.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
55.   new Main().run();  
56.  }  
57. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  boolean[] fs=new boolean[10001];
  for(int i=0; i<10001; i++){
   fs[i]=isPrime(i-2)&&isPrime(i);
  }

  for(; sc.hasNext();){
   int n=sc.nextInt();
   if(n==0){
    break;
   }
   for(; !fs[n]; n--);
   println((n-2)+" "+n);
  }
 }

 boolean isPrime(int n){
  for(int i=2; i*i<=n; i++){
   if(n%i==0){
    return false;
   }
  }
  return n>=2;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}