题目：

设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

分析：

原根的板子题了。

原根知识详解：

实现：

#include 
     
      using namespace std;typedef long long LL;const int maxn = 100000 + 131;vector
      
        Primes;bool Jug[maxn];void Make_Primes() { /// 素数打表    Primes.clear();    memset(Jug, false, sizeof(Jug));    for(LL i = 2; i <= maxn; ++i)    {        if(Jug[i] == false) {            Primes.push_back(i);            for(LL j = i + i; j <= maxn; j += i)                Jug[j] = true;        }    }}vector
       
         Pi;void GetPi(LL X) { /// 获得 x 的质因子    Pi.clear();    LL mx = Primes.size();    for(LL i = 0; i < mx && Primes[i] * Primes[i] <= X; ++i)    {        if(X % Primes[i] == 0) {            Pi.push_back(Primes[i]);            while(X % Primes[i] == 0) X /= Primes[i];        }    }    if(X > 1) Pi.push_back(X);}LL Pow(LL a, LL n, LL mod) { /// 快速幂取摸    LL ret = 1;    while(n) {        if(n & 1) ret = ret * a % mod;        a = a * a % mod;        n >>= 1;    }    return ret;}bool JugAx(LL tmp, LL P) { /// 判断 tmp 是否是 P 原根    for(int i = 0; i < Pi.size(); ++i)    {        if(Pow(tmp, (P-1)/ Pi[i], P) == 1)            return false;    }    return true;}int main() {    LL P;    Make_Primes();    while(cin >> P) {        GetPi(P-1);        for(LL i = 2; i <= P-1; ++i)        {            if(JugAx(i, P)) {                cout << i << endl;                break;            }        }    }    return 0;}