How many divisors of a set of numbers has?

Question

Let $S:=\{x_1,x_2,\dots,x_n\}$ be a finite set of natural numbers. Is there an efficient algorithm to find how many numbers divide at least one of $x_i$ in the set $S$?

For example. If $S=\{2,6,15\}$ then the divisors of each of the members are:

$$\begin{array}{rl} 2: & \{1, 2\} \\ 6: & \{1, 2, 3, 6\} \\ 15:& \{1, 3, 5, 15\} \\ \end{array}$$

If we take the union of the divisor sets, we get $\{1, 2, 3, 5, 6, 15\}$, which has $6$ elements, so the answer is $6$.

Answer 1

As an alternative to iterating over all of the divisor sets, you can use inclusion-exclusion with GCDs to handle multiple counting of divisors. If $d(n)$ is the number of divisors of $n$, then we are looking for $$ N = \sum_i d(x_i) - \sum_{i<j} d(\gcd(x_i,x_j)) + \sum_{i<j<k} d(\gcd(x_i,x_j,x_k)) - \cdots \pm d(\gcd(x_1,x_2,\ldots,x_n)) $$ This requires computing the gcd for $2^n-n-1$ subsets of $S$. We can start off by calculating $M=\sum d(x_i)$. Then if $2^n < M$ use this approach, otherwise it will be as fast just to take the union of the divisor sets as you described (the exact relative efficiency depends on how you can take the gcds and generate divisors).

e.g. in your example $n=3$ so we need to calculate 4 gcds, and $$ N = d(2)+d(6)+d(15)-d(2)-d(3)-d(1)+d(1) = 2+4+4-2-2-1+1 = 6 $$ If $S=\{12600,20580,22500\}$, then the gcd approach is much better since $\sum d(x_i)=165$. On the other hand, if $S=\{10,12,14,16,18,20,22,24,26,28,30\}$ then $\sum d(x_i)=61$ but technically we should compute $>2000$ gcds, so just finding the union of the divisor sets will be more efficient.

Answer 2

Hard to say, since you haven't defined "efficient". Since you're willing to assume the numbers are already factored, why not do as you did in your example --- find all the divisors of each of the numbers, and then take the union?