Given 2 positive integers $n, l$ with $ l \leq n$, I am looking for a way to find the largest divisor $d$ of $n$, such as $d \leq l$.
Assume $n$ has too many divisors for an exhaustive search.
Thanks in advance
I have finally found the right algorithm for this problem
(Meet in the middle algorithm
http://community.topcoder.com/tc?module=Static&d1=hs&d2=match_editorials&d3=tchs07Semi)
Thank you for all the answers.
Here is a brief description.
BTW, the factorization of $n$ is known.
I factorize $n$ in 2 parts $n=n1 \times n2$ where $n1$ and $n2$ have roughly the same number of divisors.
I generate $d1$ = the divisors of $n1$ and $d2$ = the divisors of $n2$.
The number of divisors of $n1$ and $n2$ is roughly $\sqrt {} $ number of divisors of $n $
Then I use the aformentioned algorithm using lists $d1$ and $d2$
For example: Largest divisor of $16! \le 10^{13} = 6974263296000$
public static long ClosestDivisor(long n1, long n2, long target)
{
List<long> a = Divisors(n1);
a.Sort();
List<long> b = Divisors(n2);
b.Sort();
int i1 = 0;
int i2 = b.Count - 1;
long M = long.Zero;
while (i1 < a.Count && i2 >= 0)
{
long P = a[i1] * b[i2];
if (P > target)
i2--;
else
{
if (P > M)
M = P;
i1++;
}
}
return M;
}
Philippe