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