题目链接：
51nod 1135 原根
题意：
求素数p的最小原根。
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string.h>
#include <cstring>
using namespace std;
const int MAX_N = 1000010;
typedef long long ll;int prime_cnt, factor_cnt, p;
int vis[MAX_N], prime[MAX_N], factor[MAX_N];void GetPrime()
{prime_cnt = 0;memset(vis, 0, sizeof(vis));for(int i = 2; i < MAX_N; i++){if(!vis[i]){prime[prime_cnt++] = i;for(int j = 0; j < prime_cnt && prime[j] * i < MAX_N; j++){vis[i * prime[j]] = 1;if(i % prime[j] == 0) break;}}}
}void Factor(int x)
{factor_cnt = 0;int t = (int) sqrt(x + 0.5);for(int i = 0; prime[i] <= t; i++){if(x % prime[i] == 0){factor[factor_cnt++] = prime[i];while(x % prime[i] == 0) x /= prime[i];}}if(x > 1) factor[factor_cnt++] = x;
}ll quick_pow(ll n, ll m, ll mod)
{ll res = 1, tmp = n % mod;while(m){if(m & 1) res = res * tmp % mod;tmp = tmp * tmp % mod;m >>= 1;}return res;
}void solve()
{Factor(p - 1);for(int g = 2; g < p; g++){bool flag = true;for(int i = 0; i < factor_cnt; i++){int t = (p - 1) / factor[i];if(quick_pow((ll)g, (ll)t, (ll)p) == 1){flag = false;break;}}if(flag){cout << g << endl;break;}}
}int main()
{GetPrime();while(cin >> p){solve();}return 0;
}