find number of factors of n , which are greater than k.

Question

if some n and k is given , we need to find number of factors of n , which are greater than k. i.e. if n= 14, k=5, then ans should be 2, i.e. 7 and 14. I know a sqrt(n) solution , can i improve my solution ? edit : i have a constant k and many different n.

Answer 1

If $n=\prod_{i=1}^m p_i^{a_i}$ with $a_i\in\Bbb Z_+$, then the number of all divisors of $n$ is $\prod_{i=1}^m(a_i+1)$. We need to subtract from this the number of divisors $\le k$. To this end, we enumerate these:

All variables below must be of a type capable of holding an integer in the range $0,\ldots,k$. The $k$ entries $D[0],\ldots, D[k-1]$ of array $D$ must also be of this type. Only $i$ and $a'$ could theoretically take larger values, if some of the given values $m$ and $a_i$ are $>k$.

1. Init: Set $D[0]\leftarrow 1$, $w\leftarrow 1$, $i\leftarrow 1$
2. Set $r\leftarrow w$, $a'\leftarrow a_i$, $k'\leftarrow \lfloor k/p_i\rfloor$, $j\leftarrow 0$
3. If $j=r$, let $a'\leftarrow a'-1$, $r\leftarrow w$ and go to step 6.
4. If $D[j]\le k'$, let $D[w]\leftarrow p_i\cdot D[j]$, $w\leftarrow w+1$.
5. Set $j\leftarrow j+1$
6. If $a'>0$ and $r<w$, go back to step 3.
7. If $i<m$, set $i\leftarrow i+1$ and go back to step 2
8. Terminate with the following result: $n$ has $w$ divisors $\le k$.