There is an abundant literature, and even here on MO no shortage of questions, on the question of the smallest prime primitivee root modulo $q$ (where $q$ is a prime, or more generally
an odd prime power, so that $(\mathbb Z/q \mathbb Z)^\ast$ is cyclic, and has generators, called *primitive root*). I wonder if there is any conjecture or result on the following problem:



> 
> For $q$ a prime or an odd prime power, estimate the smallest prime $n(q)$ which is **not** a primitive root modulo $q$.
> 
> 
> 


It is certainly very hard to prove any non-trivial lower bound on $n(q)$, since the statement *$n(q)>2$ for all prime $q$ sufficiently large* is clearly equivalent to the falsity of Artin's conjecture
that $2$ is a primitive root infinitely often. But what about a conjectural lower bound?
and what about upper bound?



Least non primitive root
Trivially, any upper bound for the least prime quadratic residue modulo $p$ is also an upper bound for the least prime non-primitive root modulo $q$. I can't recall what's been proved about the latter problem assuming GRH (probably a power of $\log q$), but that will form a good conjectural upper bound.


As for a conjectural lower bound, given an odd integer $n$, there are presumably infinitely many primes $q$ in any fixed residue class $a\pmod{8n}$ such that $(q-1)/2$ is also prime, as long as $a-1$ is not divisible by any prime dividing $n$. Taking $n$ to be the product of all the odd primes up to $z$, so that $n \approx e^z$, we expect to find such a prime $q$ no larger than $e^{(1+o(1))z}$. If we choose $a$ appropriately, then all primes up to $z$ will be quadratic residues modulo $q$; since $(q-1)/2$ is also prime, all quadratic residues are primitive roots. This argument gives a conjectural lower bound of about $\log q$ for the smallest prime non-primitive root.


