How can one efficiently generate n small relatively prime integers?

You can find the first n primes in time $n\log n/\log\log n$ with the Atkin-Bernstein sieve. This is better than your naive $n\log^5n$ or so algorithm (or drop the exponent by 1 using pretesting with M-R), but still superlinear.

Check out Chapter 1 of Paul Pollack's book "Not Always Buried Deep". He lists several elementary proofs for the infinitude of primes, some of which can be adapted to form simple iterative algorithms.

(Sorry, I can't get Latex to work here. Isn't it like MathOverflow? Anyway..)

Let S = {p1...pk} be the set of previously generated coprime integers.

And take M = product of integers in S

Now do any of the following to get new integer coprime to the set S.

1. (Euclid): M + 1
2. (Stieltjes): Factor M as A.B in some way, and take A + B
3. (Euler) Totient(M)
4. (Braun and Metrod): N = M/p1 + ... + M/p_k
5. (Goldbach): N = 2 + M

There is also Saidak's proof from the same book:

• Take N1=n; N2 = N1(N1+1); N3 = N2(N2+1)... Nk=Nk(Nk+1) and so on. This a relative prime sequence.

I am probably missing a couple of other proofs. Anyway, check the book!

EDIT1 : **I am going to retain the answer despite the negative votes, in the hope that it might spur someone else to invent a better algorithm ! *