I would not worry about it. The least quadratic non-residue modulo a fixed prime $q$ is also a prime, so just check the primes $2,3,5,7,11,13,17, \ldots$ in order until the Legendre symbol says you have a non-residue. The important thing is that the first non-residue is really, really small compared to the prime itself. See OEIS.
Oh, why is the first nonresidue prime? Call the prime $q$ and the first nonresidue $N.$ Since $1$ is always a residue, we have $N > 1.$ Since exactly half the numbers from $1$ to $q-1$ are residues, half nonresidues, we know $N < q.$ If $N$ were also composite, we would have $N = ab$ with $1 < a,b < N.$ Since $N$ is the smallest nonresidue, this means $a,b$ would be residues. But the product of quadratic residues is another quadratic residue, which would mean $N=ab$ would need to be a quadratic residue. This is a contradiction, so $N$ is prime.