Checking whether a number divides any of a set of other numbers

Consider a static set $S$ of positive numbers from range $[1..10^9]$. Is there an efficient algorithm to answer queries of the form: "Given a number $d$ is there an element $x \in S$ such that $d | x$".

• Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.

• Storing all the divisors for every element of $S$ makes query time $O(1)$ but uses too much memory and precomputation time $O(|S| \times \sqrt{|\max(S)|})$.

I'm interested in an algorithm that uses less memory than second solution (because $|S| \sim 10^6$) and still somewhat faster queries than first solution (number of queries is also $\sim 10^6$).

A silly answer:

Precompute the union of the sets of the factors of all elements in the set.

Then checking if the number is a divisor of any elements in the set is just a single set lookup ($O(1)$). This, however, requires an absurd amount of precomputation (and space to store the resulting set).

The precomputation time can probably be improved - sort the input set, then for each number from 1 to the square root of the largest number in the set, check if any of the numbers from the number squared to the largest number in the set are divisible by the number (add it to the cache if so). It's still absurd, however.

StackExchange Computer Science Q#48305, answer score: 2