Find a Primitive Root — Solution & Editorial
g is a primitive root iff g(P−1)/q ≠ 1 for every prime q dividing P−1. Factor P−1 once, then test g = 2, 3, ... — roots are small and dense.
Complexity: O(factorize(P−1) + answer · log)
g is a primitive root iff g(P−1)/q ≠ 1 for every prime q dividing P−1. Factor P−1 once, then test g = 2, 3, ... — roots are small and dense.
Complexity: O(factorize(P−1) + answer · log)