Remove r-th powers

Ruby, 56 characters

r,n=$<.map &:to_i;puts ([*l=1..2*n]-l.map{|i|i**r})[0,n]

Pretty straightforward (and similar to Lars' solution). Takes about 5 seconds to complete for r = 2, n = 1000000 and 8 seconds for r = 10, n = 1000000 here.

Golfscript, 18 characters

~.3*,.{3$?}%-@;<n*

Basically a direct port of my Ruby solution. Also probably not completely golfed yet, I'll take a look at it later today again.

Golfscript (18 17 chars)

~.3*,@{?}+1$%-<n*

This turns out to be similar to Ventero's solution, but slightly shorter (at time of writing!)

For a more efficient solution, 26 chars gives

~2.@{.2$4$?={)\)\}*.p)}*];

which uses the obvious algorithm:

int k = 2, x = 2;
for (i = 0; i < n; i++) {
    if (pow(k,r) == x) {k++; x++;}
    println(x++);
}