1
$\begingroup$

For a given set of numbers, I need to find the lowest common divisor that's higher than a given number, N. Is there a way to do that?

  • 0
    Do you mean the least common *multiple* that is greater than $N$?2012-10-21
  • 0
    No. I do mean a _divisor_.2012-10-21
  • 1
    @shesek Any common divisor divides the gcd and every divisor of gcd is a common divisor. Hence, what you are after is $$\min \{d| \gcd(x_1,x_2,\ldots,x_k): d > N\}$$ Is this what you are after and am I interpreting your question correctly?2012-10-21
  • 3
    I’d find the gcd $d$ of the set of numbers. If I could easily find its prime factorization, I’d do so, and from that I’d find the smallest subproduct bigger than $N$.2012-10-21
  • 0
    @Marvis I think you are, tho I'm not quite sure what that formula means (not much of a math background, I'm a programmer). Can you elaborate?2012-10-21
  • 0
    @BrianM.Scott So I would generate all the possible subproducts of the prime factors, than find the lowest one bigger than N? Or is there a better way to do that? I'm trying to implement as an software algorithm, in the most efficient way possible.2012-10-21
  • 1
    If I were programming it, I don’t think that I’d bother with the prime factors: factorization tends to be difficult. You might find that a simple search from $N+1$ to $d$, testing each number to see whether it divides $d$ and picking the first hit, is the way to go.2012-10-21
  • 0
    Actually, I think I found another way to accomplish what I'm trying to implement in my software. I asked at http://math.stackexchange.com/q/218210/45513. Thanks for all the help!2012-10-21

0 Answers 0