Aizu Online Judge 0185 Goldbach's Conjecture II

■0185 Goldbach's Conjecture II

入力が最大で10⁶なので，最初にエラトステネスの篩で素数を生成しておくのが無難．

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.  int n;  
17.  int max=1000000;  
18.  int[] prime;  
19.  boolean[] isPrime;  
20.   
21.  void run(){  
22.   int p=0;  
23.   prime=new int[max];  
24.   isPrime=new boolean[max+1];  
25.   Arrays.fill(isPrime, true);  
26.   isPrime[0]=isPrime[1]=false;  
27.   for(int i=2; i<=max; i++){  
28.    if(isPrime[i]){  
29.     prime[p++]=i;  
30.     for(int j=2*i; j<=max; j+=i){  
31.      isPrime[j]=false;  
32.     }  
33.    }  
34.   }  
35.   
36.   for(;;){  
37.    n=sc.nextInt();  
38.    if(n==0){  
39.     break;  
40.    }  
41.    int ans=0;  
42.    for(int i=0; i<p; i++){  
43.     if(prime[i]>n/2){  
44.      break;  
45.     }  
46.     if(isPrime[n-prime[i]]){  
47.      ans++;  
48.     }  
49.    }  
50.    println(""+ans);  
51.   }  
52.  }  
53.   
54.  void debug(Object... os){  
55.   System.err.println(Arrays.deepToString(os));  
56.  }  
57.   
58.  void print(String s){  
59.   System.out.print(s);  
60.  }  
61.   
62.  void println(String s){  
63.   System.out.println(s);  
64.  }  
65.   
66.  public static void main(String[] args){  
67.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
68.   new Main().run();  
69.  }  
70. }  

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;

 int n;
 int max=1000000;
 int[] prime;
 boolean[] isPrime;

 void run(){
  int p=0;
  prime=new int[max];
  isPrime=new boolean[max+1];
  Arrays.fill(isPrime, true);
  isPrime[0]=isPrime[1]=false;
  for(int i=2; i<=max; i++){
   if(isPrime[i]){
    prime[p++]=i;
    for(int j=2*i; j<=max; j+=i){
     isPrime[j]=false;
    }
   }
  }

  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   int ans=0;
   for(int i=0; i<p; i++){
    if(prime[i]>n/2){
     break;
    }
    if(isPrime[n-prime[i]]){
     ans++;
    }
   }
   println(""+ans);
  }
 }

 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();
 }
}