I know that rand() % N would be able to generate a long integer between 0 and N-1 if N is not too large. However, now I'd lke to generate about 0.1N number of integers from 0 to N-1, would there be some quick way to do this?

When N is small, it might be possible to keep an array and check if the number has been generated before, but this becomes very slow as N increases. Moreover, with a poor seed it might even generate the same number over and over again and form a dead loop.

Also, I guess it is possible to use hashing to distribute the number, and open addressing just simply makes every generated number go to the next empty spot (for instance, if 23 is generated twice, try 23+4, 23+9, 23+16...) But this, too, is slow for large datasize.

So, is there any good way to generate a bunch of disjoint random numbers in acceptable time? Thank you!

P.S.the size of N is quite large, at least at the order of 10^6-10^7, and would be best if it can run at 10^8. (Actually the problem is a boolean array of N, and flip randomly 10% of it) If a "shuffling" algorithm can be implemented it will also work.