Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
All positive divisors of a number | Reply
n = p_1^e_1 * p_2^e_2 * p_3^e_3 * ... * p_k^e_k

Is there an algorithm, better than bruteforce O(sqrt(n)) to iterate all divisors of n, given its factorization?

Backtracking definitely does it, however, is there a nice trick to code this?
Re: All positive divisors of a number (response to post by ntn) | Reply
Backtracking definitely does it, however, is there a nice trick to code this?

Yes. In fact, backtracking is what I used to generate all factors for the div1 500 in SRM 378. Look at the try_divisors function here. I keep the divisor built so far in the variable val.

(EDIT: Don't worry -- the code failing does not involve a bug in the try_divisors function, which has been verified by a practice room resubmission)
Re: All positive divisors of a number (response to post by ntn) | Reply
I believe this general concept works

vector<int> divisors(1, 1);
for(int i = 0; i < k; i++)
{
    int n = divisors.size();
    for(int j = 0; j < e[i]; j++)
    {
        for(int k = 0; k < n; k++)
        {
            divisors.push_back(p[i] * divisors[k + j * n]);
        }
    }
}
Re: All positive divisors of a number (response to post by msg555) | Reply
Your method is very nice, however, it takes about 30s for [1, 1000000]. After changing divisors to array, it takes 0.8s, even faster than my backtracking(1.07s) on my machine.

Thank you very much !!!

Here is my code using array:
int cnt = 1, divisors[10000]; divisors[0] = 1; // fixed by msg555
for (int i = 0; i < k; i++){
  int n = cnt;
  for (int j = 0; j < e[i]; j++)
    for (int k = 0; k < n; k++) divisors[cnt++] = p[i] * divisors[k + j * n]; 
}
Re: All positive divisors of a number (response to post by Minilek) | Reply
Thanks, I should test my code with that problem. :)
Re: All positive divisors of a number (response to post by ntn) | Reply
It should be

int cnt = 1, divisors[200]; divisors[0] = 1;
Re: All positive divisors of a number (response to post by msg555) | Reply
To set the size of the array for divisors, I ran into a new problem.

What is the maximum number of divisors that a number in [1, 1000000000] has?

There is a clear bound O(sqrt(n)).

It took about 3 minutes to bruteforce the exact number in the range[1, 10000000].
Re: All positive divisors of a number (response to post by ntn) | Reply
I think O(n^{1/3}) is also a valid bound but I'm not 100% sure.
Re: All positive divisors of a number (response to post by gawry) | Reply
Edit: I was mistaken, an asymptotic bound for the AVERAGE number of divisor is O(log n). d(n) = ln n + 2*gamma - 1 + o(1), where gamma is Euler's constant. gamma = lim_{n->inf}(H(n)-ln n)
Re: All positive divisors of a number (response to post by sclo) | Reply
Are you sure? I think it should grow faster than poly log(n).

For any fixed k, consider the number n=2^x*3^x*...*(p_k)^x. This number has roughly x^k divisors, which, since n is 2^O(x), is Omega(log(n)^k).
Re: All positive divisors of a number (response to post by gawry) | Reply
http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper8/page1.htm

It follows that it is O(n^epsilon) for all epsilon.
Re: All positive divisors of a number (response to post by msg555) | Reply
for(int i = 0; i < k; i++)

what's the initial value of k?

Would you mind explaining the idea behind your code? It seems quite strange...
Re: All positive divisors of a number (response to post by trulo_17) | Reply
p,e,k are from the original post by ntn.
Re: All positive divisors of a number (response to post by trulo_17) | Reply
heh, now that I think about it, I re-used k which could be a bit confusing.

The code may make more sense as
int cnt = 1, divisors[10000]; divisors[0] = 1;
for (int i = 0; i < k; i++){
  int n = cnt;
  for (int j = 0; j < e[i]; j++)
    for (int a = 0; a < n; a++) divisors[cnt++] = p[i] * divisors[a + j * n]; 
}


p is an array of primes
e is the exponent on each of those primes
k is the number of elements in p and e

Basically the idea is to calculate all the previous divisors * p, then use those values to calculate all previous divisors * p^2, etc... I could just keep track of p[i]^j but this way ends up being a bit shorter/cleaner.

It's kind of cool, with the algorithm laid out like this it is really obvious where the formula for the number of divisors given a prime factorization comes from.
Re: All positive divisors of a number (response to post by tomek) | Reply
Since it is O(poly(log n)), it is O(n^epsilon) for all epsilon > 0.

Is it too much to ask a general question for an interval [a, b]?

Given [a, b], what is the maximum number of divisors that a number in [a, b] has?

Which difficulty level do you think this problem is in a SRM: easy, medium, or hard?

Example:
Input [1, 10000000]
Output 448

BTW, my question in the second post is the output of [1, 1000000000]. And, so far, I only see the need of a = 1.
[ 1 2 ]    NEXT >

RSS