How can one efficiently generate n small relatively prime integers? The definition of small is that they have O(lg n) bits. One way is just to test the integers 2,3,... for primality and keep the first n primes, but this takes at least O(n log n) time (times the cost of primality testing) using a naive algorithm. Is it possible to do it in linear time?
 A: 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.
A: 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.


*

*(Euclid): M + 1 

*(Stieltjes): Factor M as A.B in some way, and take A + B

*(Euler) Totient(M)

*(Braun and Metrod): N = M/p1 + ... + M/p_k

*(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 ! *
A: See this "Generating All Co-Prime Pairs".
Method claims to be complete and yield no repeats.  Each result generates THREE new children; just stop the generation if either member of the (m, n) pair exceed your definition of "small".
Since this is a declarative generation, that meets your criterion for "linear time", right?
To my (non-mathematician) eyes, this relationship looks a lot like generating Pythagorean-triples.
A: I assume S need not be prime (just relatively prime)
For S= {2, 15}
Goldbach method : N = 2 + M
                = 2 + 30

                = 32 (not relatively prime with 2)

