How to efficiently find the last remaining random numbers in a set

Given a range of numbers, say 1 to 1,000,000, it's easy to generate a bunch of random ones:

var size = 1000 // so browser doesn't crash, smaller set
var i = size * .95
var map = {}
while (i--) {
  var number = Math.floor(Math.random() * size)
  if (map[number]) {
    i++
  } else {
    map[number] = true
  }
}

var numbers = Object.keys(map)
console.log(numbers)

That generates 95% of the numbers.

The question is, how to efficiently find the remaining numbers without brute-force checking (e.g. without doing what this algorithm is already doing, going through and randomly generating a number and seeing if there is already a match).

Given:

1. You know all numbers that have already been found.
2. The already generated numbers are randomly distributed.
3. You want to find the remaining numbers efficiently.
4. Assume the set of remaining numbers is small compared to the number of existing numbers.
5. Under the assumption that the size of the numbers can be up to 2048 bit number, or 1 with 617 zeroes, so it's not possible to enumerate all of the values efficiently.

Wondering the following:

1. What is the O-notation of a better algorithm that can be found (if any is known).
2. If there is a computer science approach to solving this problem, given a better O-notation.

It seems like there might be a way to do a divide and conquer or sorting strategy, but this seems like a complex problem that probably has already been solved effectively.