number of divisors of a number which are not smaller than another number

Question

Is there any efficient way to find the number of divisors of a number (say n) which are not smaller than another number (say m). n can be up to 10^12. i thought about sieve algorithm & then find the number of divisors. my method check all the numbers from m to square root of n. But i think there is another way(efficient) to do that .

Answer 1

It's easy to find the divisors of a number if you know the prime factors; just take all possible combinations of the multiplicities of all the factors.

For n as small as 10^12, trial division should be a sufficiently fast factorization method, as you only have to check potential factors up to 10^6.

Edit: add discussion about "all possible combinations" and factoring by trial division.

Consider the number 24505 = 5 * 13 * 13 * 29. To enumerate its divisors, take all possible combinations of the multiplicities of all the factors:

5^0 * 13^0 * 29^0 = 1
5^0 * 13^0 * 29^1 = 29
5^0 * 13^1 * 29^0 = 13
5^0 * 13^1 * 29^1 = 377
5^0 * 13^2 * 29^0 = 169
5^0 * 13^2 * 29^1 = 4901
5^1 * 13^0 * 29^0 = 5
5^1 * 13^0 * 29^1 = 145
5^1 * 13^1 * 29^0 = 65
5^1 * 13^1 * 29^1 = 1885
5^1 * 13^2 * 29^0 = 845
5^1 * 13^2 * 29^1 = 24505

It's also not hard to factor a number by trial division. Here's the algorithm, which you can translate to your favorite language; it's plenty fast enough for numbers up to 10^12:

function factors(n)
    f = 2
    while f * f <= n
        if n % f == 0
            output f
            n = n / f
        else
            f = f + 1
    output n

Let's look at the factorization of 24505. Initially f is 2, but 24505 % 2 = 1, so f is incremented to 3. Then f = 3 and f = 4 also fail to divide n, but 24505 % 5 = 0, so 5 is a factor of 24505 and n is reduced to 24505 / 5 = 4901. Now f = 5 is unchanged, but it fails to divide n, likewise 6, 7, 8, 9, 10, 11 and 12, but finally 4901 % 13 = 0, so 13 is a factor of 4901 (and also 24505), and n is reduced to 4901 / 13 = 377. At this point f = 13 is unchanged, and 13 is again a divisor, this time of the reduced n = 377, so another factor of 13 is output and n is reduced to 29. At this point 13 * 13 = 169 is greater than 29, so the while loop exits, and the final factor of 29 is output; this works because if n=pq, then one of p or q must be less than the square root of n (except in the case where p and q are equal and n is a perfect square), and since we have already done trial division by all the p and q less than the square root of 29, it must be prime, and thus the final factor. So we see that 24505 = 5 * 13 * 13 * 29.

I discuss these kinds of algorithms in my essay Programming with Prime Numbers.

Answer 2

Following is an example program that computes the number of divisors of n that are larger than m. The largeDivs() code runs in time O(c) if there are c divisors. largeDivs() also starts with a representation of n as a factored number, with nset being a list of pairs of form (p_i, k_i) such that n = Product{p_i**k_i for i in 1..h}. Some example output is shown after the program. The check() routine is used to demonstrate that largeDivs() produces correct results. check() takes a long time for smaller values of m.

def largeDivs(n, nset, m):
    p, k = nset[-1]
    dd = 0
    if len(nset) > 1:
        nn, mm = n / p**k, m
        for i in range(k+1):
            dd += largeDivs(nn, nset[:-1], mm)
            mm = (mm + p-1)/p
    else:
        c, v = k+1, 1
        while v<m and c>0:
            c, v = c-1, v*p
        return c
    return dd

def check (n,m,s):
    if m<1:
        return s
    c = 0
    for i in range(m,n+1):
        if (n%i)==0:
            c += 1
    return c


tset = [(2,3),(3,2),(11,1),(17,1),(23,2)]
n = s = 1
for i in tset:
    s *= 1+i[1]
    n *= i[0]**i[1]
print 'n=',n, '  s=',s
m=0
for i in range(8):
    print 'm:', m, '\t', largeDivs(n, tset, m), '  Check:',check(n,m,s)
    m = 10*m + 5

Example output:

n= 7122456   s= 144
m: 0    144   Check: 144
m: 5    140   Check: 140
m: 55   124   Check: 124
m: 555  95   Check: 95
m: 5555     61   Check: 61
m: 55555    28   Check: 28
m: 555555   9   Check: 9
m: 5555555  1   Check: 1

Answer 3

It depends on the application, but if performance is such an issue I'd use a pre-generated hash table. Obviously 10^12 entries might be impractical (or at least undesirable) to store in memory, so I'd do division tests up to the k^th prime number, generating hash table entries only for numbers not divisible by those first k prime numbers.

For example, though crudely written and untested, this should give you an idea:

int   number   = 23456789;
int   primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 0};
int   pfactors = 0;
int*  prime = primes;
float temp;

// check until we reach the end of the array (0)
while (prime)
{
    // divide by prime and check if result is integer
    temp = (float)number/*prime;
    if (temp == floor(temp))
    {
        // if so, increment count of prime factors and loop (same prime again!)
        pfactors++;
        number = (int)temp;
    }
    else
    {
        // else try the next prime
        prime++;
    }
}

// finally, rely on hash table magic
pfactors += pregenerated_hash[number];