2
$\begingroup$

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

  • 1
    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.2012-06-21
  • 0
    Lets assume that the numbers have been factored already.2012-06-21
  • 0
    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.2012-06-21

2 Answers 2

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

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.

1

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?