LightOJ 1024 - Eid http://lightoj.com/volume_showproblem.php?problem=1024 求n个数的最大公约数，分解质因子，统计质因子。

LigthOJ1024.java

import java.io.BufferedReader;
import java.io.IOError;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;

public class P1024 {

        int[] prime = new int[10010];
	boolean[] check = new boolean[10010];
	int cnt = 0;

	void getPrime() {
		for (int i = 2; i < 10010; i++) {
			if (check[i] == false)
				prime[cnt++] = i;
			for (int j = 0; j < cnt; j++) {
				if (prime[j] * i >= 10010)
					break;
				check[i * prime[j]] = true;
			}
		}
	}

	public void run() {
		Scanner cin = new Scanner(System.in);
		PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));

		getPrime();
		int[] tot = new int[10010];
		int test = cin.nextInt();
		for (int cas = 1; cas <= test; cas++) {
			cout.print("Case " + cas + ": ");
			int n = cin.nextInt();
			Arrays.fill(tot, 0);
			for (int num = 0; num < n; num++) {
				int x = cin.nextInt();
				int tmp = x;
				for (int i = 0; i < cnt; i++) {
					int count = 0;
					while (tmp % prime[i] == 0) {
						tmp /= prime[i];
						count++;
					}
					if (tot[prime[i]] < count)
						tot[prime[i]] = count;
				}
			}
			BigInteger res = BigInteger.ONE;
			for (int i = 2; i < 10010; i++) {
				if (tot[i] > 0) {
					res = res.multiply(BigInteger.valueOf(i).pow(tot[i]));
				}
			}
			cout.println(res);
			System.gc();
		}

		cout.flush();
	}

	public static void main(String args[]) {
		new P1024().run();
	}

	class Scanner {

		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
			eat("");
		}

		void eat(String s) {
			st = new StringTokenizer(s);
		}

		String nextLine() {
			try {
				return br.readLine();
			} catch (IOException e) {
				throw new IOError(e);
			}
		}

		boolean hasNext() {
			while (!st.hasMoreTokens()) {
				String s = nextLine();
				if (s == null)
					return false;
				eat(s);
			}
			return true;
		}

		String next() {
			hasNext();
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}
	}

}