Primitive root

/*
 Finds primitive root modulo n which is an integer g such that g^k (mod n) covers all elements from 1 to n such that gcd(a,n) = 1
 It exists only for n = 1,2,4 or (odd prime)^k or 2*(odd prime)^k and in such case no. of primitive root modulo n is phi(phi(n))
 Algo here uses the idea that g^(phi(n)) = 1 (mod n) and no other integer smaller than phi(n) holds this.
 
 int phi(int n) { // Calculates phi(n) in O(√n) time
    int result = n;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0)
                n /= i;
            result -= result / i;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
ll powmod(ll a,ll b,ll mod) {ll res=1%mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res%mod;}

int primitive_root(int n){
     int p = phi(n), x = p;
     vector<int> fac;
     for(int i = 2; i*i <= x; ++i ){
          if(x%i==0){
              while(x%i==0)  x/=i;
              fac.pb(i);
          }
     }
     if(x>1) fac.pb(x);
     for(int i = 2;i<=p;++i){
        bool ok = 1;
        for(int j = 0; j < fac.size() && ok; ++j)
            ok &= powmod(i,p/fac[j],n);
        if(ok) return i;
     }
     return -1;
}