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?
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.
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)