If p is prime it has a primitive root, lots of them.  Try a couple values at random; you're sure to run into one.  If g is primitive, and q is a prime dividing p-1, then g^(p-1)/q will not be 1 mod p.  We haven't gone through the entire cycle.  Conversely, assume g^p-1 is 1, but the exponents (p-1)/q don't produce 1.  If g^k = 1 then k divides p-1, yet it doesn't divide (p-1)/q for the primes q in p-1, so k can't be a proper factor of p-1.  G generates a cycle of length p-1.  All the nonzero elements are units; they are all coprime to p.  Hence p is prime.