原根

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1135

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）
给出1个质数P，找出P最小的原根。

Input

输入1个质数P(3 <= P <= 10^9)

Output

输出P最小的原根。

Input示例

3

Output示例

2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.ArrayList;

public class Main {
	static ArrayList<Integer> prime = getPrime(1000000);
	static ArrayList<Integer> sprime = new ArrayList<>();// 存储P-1的素因子

	public static void main(String[] args) throws IOException {
		StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(System.out);
		in.nextToken();
		int p = (int) in.nval;
		divide(p - 1);
		for (int g = 2; g < p; g++) {
			boolean flag = true;
			for (int i = 0; i < sprime.size(); i++) {
				int t = (p - 1) / sprime.get(i);
				if (quickPowerMod(g, t, p) == 1) {
					flag = false;
					break;
				}
			}
			if (flag) {
				out.println(g);
				break;// 去掉break的话是求所有的原根，加上break是求最小的原根、
			}
		}
		out.flush();
	}

	static void divide(int n) {
		// 将n分解为素因子
		int t = (int) Math.sqrt(n);
		for (int i = 0; prime.get(i) <= t; i++) {
			if (n % prime.get(i) == 0) {
				sprime.add(prime.get(i));
				// 因为有可能有多个prime[i]
				while (n % prime.get(i) == 0) {
					n /= prime.get(i);
				}
			}
		}
		if (n > 1) {
			sprime.add(n);// 可能只有自己一个素因子
		}
	}

	static long quickPowerMod(long x, long n, long mod) {
		long result = 1;
		while (n > 0) {
			x = x % mod;
			if ((n & 1) != 0)
				result = result * x % mod;
			x = x * x % mod;
			n >>= 1;
		}
		return result;
	}

	static ArrayList<Integer> getPrime(int n) {
		boolean[] notPrime = new boolean[n + 1];
		int sqrtN = (int) Math.sqrt(n);
		for (int i = 2; i <= sqrtN; i++) {
			if (notPrime[i])
				continue;
			for (int j = i * i; j <= n; j += i) {
				// j是i的倍数，即不是素数
				notPrime[j] = true;
			}
		}

		ArrayList<Integer> prime = new ArrayList<>();
		if (n > 1)
			prime.add(2);
		for (int i = 3; i <= n; i += 2) {
			if (notPrime[i])
				continue;
			prime.add(i);
		}
		return prime;
	}
}