Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.