Number of divisors in a given range

388 Views Asked by At

What is the best (or close) way to calculate the number of divisors of N which are in the closed integer interval [X, Y]?

As of now, the best method I know is to get all primes till $\sqrt N$, get N's prime factors and their powers and step through each possible combination inside the interval.

Edit - I had no idea that the method to choose strongly varied based on the nature of N, A, B. Originally intended for all N, A, B around $10^5$ to $10^6$, but can you answer for other ranges as well?

1

There are 1 best solutions below

1
On

This is too vague, you'll need to be more specific on the size of $X$ and $Y$. If, for example, $X=1$ and $Y=N$, the best you can do is factorize $N$ and the best way known to the date to factorize $N$ depends of the size of $N$ (trial division, Pollard's rho, quadratic sieve). On the other hand, if the length of the interval $[X,Y]$ is "small" compared to $N$, you'll do better testing each element of $[X,Y]$, here you could use wheel factorization to discard some numbers (for example, if $N$ is odd it will not have even divisors). Also, the position of $[X,Y]$ relative to $[1,N]$ will be of consideration (for example, there is no divisors of $N$ in the interval $(N/2,N)$).

The theorems and algorithms for this kind of questions often impose some kind of conditions for $X$ and $Y$ to be able to prove something useful.