JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm All positive divisors of a number [ 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_kIs 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 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.htmIt 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 primese is the exponent on each of those primesk is the number of elements in p and eBasically 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 448BTW, my question in the second post is the output of [1, 1000000000]. And, so far, I only see the need of a = 1.
 Forums Algorithm Discussions Skill-building and Educational Discussion for Algorithm All positive divisors of a number Previous Thread  |  Next Thread [ 1 2 ]    NEXT >