Take the 2-minute tour ×

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

share|improve this question
In the limit where the input numbers get large, this would (almost certainly) involving factoring the numbers, which is believed to be a hard problem. –  Henning Makholm Jun 21 '12 at 11:40
Lets assume that the numbers have been factored already. –  tzador Jun 21 '12 at 11:42
I'm not sure if this is a "good algorithm," but you can find the divisors of $\mathrm{lcm}(x_1,\ldots,x_n)$ which must be a superset, then check which ones need to be excluded. –  Zander Jun 21 '12 at 11:46

2 Answers 2

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.

share|improve this answer

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?

share|improve this answer

Your Answer


