An answer to this question on Stack Overflow.

Question

Given two numbers n and k, find x, 1 <= x <= k that maximises the remainder n % x.

For example, n = 20 and k = 10 the solution is x = 7 because the remainder 20 % 7 = 6 is maximum.

My solution to this is :

int n, k;
cin >> n >> k;
int max = 0;
for(int i = 1; i <= k; ++i)
{
  int xx = n - (n / i) * i; // or int xx = n % i;
  if(max < xx)
    max = xx;
}
cout << max << endl;

But my solution is O(k). Is there any more efficient solution to this?

Answer

waves hands around

No value of x which is a factor of n can produce the maximum n%x, since if x is a factor of n then n%x=0.

Therefore, you would like a procedure which avoids considering any x that is a factor of n. But this means you want an easy way to know if x is a factor. If that were possible you would be able to do an easy prime factorization.

Since there is not a known easy way to do prime factorization there cannot be an "easy" way to solve your problem (I don't think you're going to find a single formula, some kind of search will be necessary).

That said, the prime factorization literature has cunning ways of getting factors quickly relative to a naive search, so perhaps it can be leveraged to answer your question.