Find a Primitive Root

Difficulty: 2300 4000 ms 128 MB

number-theory

Print the SMALLEST primitive root modulo prime P — the smallest g whose powers generate every non-zero residue.

Input: one integer P (prime).

Output: the smallest primitive root.

Constraints:

• 2 ≤ P ≤ 10⁷, P prime

Sample Tests

7

3

2

1

Read the Editorial