Random number relatively prime to an input

What's a computationally sane way to, given a natural number n, generate a random number that is relatively prime to n?

I开发者_JS百科'm willing to sacrifice some randomness and coverage of all possibilities for speed. That is, if I only ever hit perhaps 75% of the possible (smaller) relative primes, that's fine.

---

"I'm willing to sacrifice randomness and coverage of all possibilities for speed." Given n, select n+1.

You're going to need to be more specific.

---

The probability that two random integers are relatively prime to one another works out to 6/pi^2 (in the limit, for large N), or approximately 61%. So generate-and-test should be a viable strategy -- the GCD calculation is about O(log n), and you will probably get a result in 2 or 3 trials.

---

in simple words:

unsigned random_prime(unsigned n){
     unsigned r = rand(), t;
     while ((t = gcd(r, n)) > 1)
         r /= t;
     return r;
}