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)
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];
}
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)
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.
