Andrea Ambu - 6 months ago 20

Python Question

Here's the very dumb way:

`def divisorGenerator(n):`

for i in xrange(1,n/2+1):

if n%i == 0: yield i

yield n

The result I'd like to get is similar to this one, but I'd like a smarter algorithm (this one it's too much slow and dumb :-)

I can find prime factors and their multiplicity fast enough.

I've an generator that generates factor in this way:

(factor1, multiplicity1)

(factor2, multiplicity2)

(factor3, multiplicity3)

and so on...

i.e. the output of

`for i in factorGenerator(100):`

print i

is:

`(2, 2)`

(5, 2)

I don't know how much is this useful for what I want to do (I coded it for other problems), anyway I'd like a smarter way to make

`for i in divisorGen(100):`

print i

output this:

`1`

2

4

5

10

20

25

50

100

Calculating all divisors of 100000000 took 0.01s with his way against the 39s that the dumb way took on my machine, very cool :D

Answer

Given your factorGenerator function, here is a divisorGen that should work:

```
def divisorGen(n):
factors = list(factorGenerator(n))
nfactors = len(factors)
f = [0] * nfactors
while True:
yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
i = 0
while True:
f[i] += 1
if f[i] <= factors[i][1]:
break
f[i] = 0
i += 1
if i >= nfactors:
return
```

The overall efficiency of this algorithm will depend entirely on the efficiency of the factorGenerator.

Source (Stackoverflow)

Comments