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

Question

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$".

1. Simple straightforward check takes $O(|S|)$ time per query and uses $O(|S|)$ memory.
2. 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$).

Answer 1

With the following techniques, I have been able to achieve a speedup of 100,000x over the brute force method of storing the dividend in an array and checking each dividend each time a divisor needs to be checked.

To do this, I use 10-20x as much working space as the brute force method when I am pre-processing the set of dividends. In the end, I use roughly 2-3x as much storage as the brute force method. I believe the working space requirement can be reduced substantially (see below) by the use of more complex algorithms.

To be specific about timing, with $\sim10^6$ dividends and divisors, the brute force method takes $0.02 \mu s$ for each dividend (that's the build) and $16{,}000{,}000 \mu s$ per divisor (that's the query) while my method takes $55 \mu s$ per dividend and the same time per divisor.

To create the structure, first make a trie of the dividends. Treat them as strings of prime factors, biggest factor first. Thus, 650 would be inserted into the trie as the string $\langle 13,5,5,2 \rangle$. Insert not only that string, but also all subsequences. In this case, that means to also insert:

• $\langle \rangle$
• $\langle 13 \rangle$
• $\langle 13,5 \rangle$
• $\langle 13,5,5 \rangle$
• $\langle 13,5,5,2 \rangle$ (the first sequence)
• $\langle 13,5,2 \rangle$
• $\langle 13,2 \rangle$
• $\langle 5 \rangle$
• $\langle 5,5 \rangle$
• $\langle 5,5,2 \rangle$
• $\langle 5,2 \rangle$
• $\langle 2 \rangle$

This represents all divisors of the dividend 650. Since all divisors are in the trie, queries can now proceed by just factoring the divisor in the same way (as a list of prime factors, largest first) and then traversing the trie. If the traversal hits a dead end before the divisor's prime sequence is exhausted, it divides no dividend in the trie.

Space-wise, for $\sim10^6$ random 31-bit dividends, this takes up 7-10x as much space as just storing the dividends themselves.

Sidebar: This is roughly the same amount of space as storing every divisor of every dividend in a hash table. I find this interesting on its own, as this is much less than the $n \sqrt{n}$ or $n \sqrt[3]{n}$ space upper bounds posted in the question and comments, I suspect because of overlap - 2 divides many numbers, but it only needs to be stored once. This method uses $60\mu s$ per dividend and $0.3\mu s$ per divisor on my computer, making about twice as fast as this trie/DAG method, while using the same amount of working space but larger storage space during queries.

To decrease the space usage of the tree, make a compressed acyclic graph of it, using the algorithm from "Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings", by Jan Daciuk. The big ideas, as I see them, are to:

1. Make an equivalence relation on DAG/Trie nodes in which two nodes are equivalent if they have the same set of children pointing to the same literal nodes. This makes deciding trie equality take time proportional to the number of children of a node, not the number of descendants. This is very important.

2. Use a postorder traversal to dedupe the nodes, so that the children of a node are already deduped before the parent, ensuring the equivalence relation doesn't miss anything.

This reduces the number of notes in the Trie/DAG by a factor of 6ish in my testing. Note that this does not do nearly as well if the prime factor strings are inserted smallest-prime first. I think that's due to the nature of the minimum automaton, in which nodes with the same label nearer to the root have many outgoing edges. Putting larger primes nearer the root reduces the amount of duplication near the root. I suspect this is related to the problem of picking a variable ordering in Binary Decision Diagrams.

In my testing, 80-90% of the work of the algorithm is actually the problem of factoring the numbers. I used trial division; if you use a better algorithm, I think your algorithm will be faster.

The working space required can be reduced using "Incremental construction of minimal acyclic finite state automata", by Daciuk et al.

In the below table, the space bounds are the amount of memory used divided by the number of items, and time bounds are the number of microseconds divided by the number of items.

$$ \begin{array}{|c|c|c|c|c|} \hline \textbf{Method} & \textbf{Construction time ($\mu s$)} & \textbf{Query time ($\mu s$)} & \textbf{Working space} & \textbf{Storage space}\\ \hline \text{Query every dividend} & 0.02 & 16{,}000{,}000 & 1 & 1\\ \hline \text{Store every divisor} & 60 & 0.3 & 7-10 & 7-10\\ \hline \text{This method} & 55 & 55 & 7-10 & 2-3\\ \hline \text{Incremental minimization} & ? & 55 & 2-3 & 2-3\\ \hline \end{array} $$

Answer 2

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.

Answer 3

Sure, there are efficient algorithms. There's a straightforward algorithm, and it is already efficient. Let $S$ be your set, and $d$ be the number.

• For each $x \in S$:

  • Check whether $d$ is a divisor of $x$, using integer division or modular arithmetic (reduce $x$ modulo $d$ and check whether you get 0). If it is, output "Yes".

• If you made it through the entire loop and no $x$ was a multiple of $d$, output "No".

There are efficient algorithms for division; they take at most quadratic time (in the bit-length of the integers), but even faster ones are known. Multiply this by the number of elements of the set $S$, and you have the running time of this algorithm.

---

You can't expect to find a solution that uses less memory. Any solution will have to store the entire set $S$, or at least something that's information-theoretically equivalent to the set of prime divisors of $S$; in the worst case, the latter is of the same size as $S$.

Answer 4

Create an Array of size 10^9 (initialized to 0). 

For each x in S: Set Array[x] = 1

currentNumber = 1

while True: 
    if d*currentNumber > 10^9 then output NO and exit
    if Array[d*currentNumber] == 1 then output YES and exit 
    else currentNumber=currentNumber+1;
output NO;