Aizu Online Judge 0202 At Boss's Expense

■0202 At Boss's Expense

可能な合計金額と，素数全列挙．

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

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, x;
 int[] a;

 void run(){
  for(;;){
   n=sc.nextInt();
   x=sc.nextInt();
   if((n|x)==0){
    break;
   }
   a=new int[n];
   for(int i=0; i<n; i++){
    a[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int max=1000000;
  int p=0;
  int[] prime=new int[max];
  boolean[] 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;
    }
   }
  }
  boolean[] dp=new boolean[max+1];
  dp[0]=true;
  for(int j=0; j<n; j++){
   for(int i=a[j]; i<=max; i++){
    dp[i]|=dp[i-a[j]];
   }
  }
  int ans=0;
  for(int i=2; i<=x; i++){
   if(dp[i]&&isPrime[i]){
    ans=i;
   }
  }
  if(ans>0){
   println(ans+"");
  }else{
   println("NA");
  }
 }

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