2769 Reduced ID Numbers

「2769 Reduced ID Numbers」の編集履歴（バックアップ）一覧はこちら

「2769 Reduced ID Numbers」(2006/05/14 (日) 00:58:23) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2769 Reduced ID Numbers
**解答例
 import java.util.*;
 
 public class Main {
     static final int SIZE = 2000;
     static int[] primetable;
     public static void main(String[] args) {    
         //make prime number table
         makePrimeTable();
         
         //scanner
         Scanner sc = new Scanner(System.in);
     
         //solve
         int x;
         while((x = sc.nextInt())!=0){
             int ans = 0;
             for(int i=0;i<SIZE;i++){
                 int sum = 0;
                 for(int j=i;j<SIZE;j++){
                     sum += primetable[j];
                     if(x==sum){
                         ans++;
                         break;
                     }
                     if(x<sum) break;
                 }
             }
             System.out.println(ans);
         }
     }
     private static void makePrimeTable(){
         primetable = new int[SIZE];
         int i = 0;
         int x = 2;
         
         boolean flag;
         while(i<SIZE){
             flag = false;
             for(int j=0;j<i;j++){
                 if(x%primetable[j]==0){
                     x++;
                     flag = true;
                     break;
                 }
             }
             if(flag) continue;
             
             primetable[i] = x;
             //System.out.println(x);
             i++;
             x++;
         }
     }
 }

**2769 Reduced ID Numbers
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         // TODO Auto-generated method stub
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         for(int i=0;i<n;i++){
             int g = sc.nextInt();
             int a[] = new int[g];
             for(int j=0;j<g;j++){
                 a[j] = sc.nextInt();
             }
             Arrays.sort(a);
 
             boolean[] ans = new boolean[1000000];
             Arrays.fill(ans, true);
             ans[0] = false;
             
             if(g==1) System.out.println(1);
             else{
                 for(int k=0;k<g;k++){
                     for(int l = k+1;l<g;l++){
                         int x = a[l] - a[k];
                         if(ans[x]==false) continue;
                         for(int m=1;m*m<=x;m++){
                             if(x%m==0){
                                 ans[m] = false;
                                 ans[x/m] = false;
                             }
                         }
                     }
                 }
                 
                 for(int m=1;m<=1000000;m++){
                     if(ans[m]){
                         System.out.println(m);
                         break;
                     }
                 }
             }
         }
     }
 }