UVa : 11827 - Maximum GCD

問題概要

http://uva.onlinejudge.org/external/118/11827.html
N個の整数が与えられる.
これらの中から2個の数を選択しGCDを取るとき, GCDの値の最大値を答えよ.

アルゴリズム

素直に実装しました.
2個の数字をどれにするか二重ループで選択して, GCDの計算結果で最大値を更新します.

プログラム

Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());

while(T-- > 0){
  String[] s = sc.nextLine().split(" +");
  int n = s.length;
  BigInteger ans = BigInteger.ZERO;
  for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
      BigInteger gcd = new BigInteger(s[i]).gcd(new BigInteger(s[j]));
      if(ans.compareTo(gcd) < 0){
        ans = gcd;
      }
    }
  }
  System.out.println(ans);
}