4 ms·
The generator is already maintaining a dictionary containing multiple lists that hold all the primes found so far. Even if it instead kept yielding a list of al
by kmill 3y ago
The generator is already maintaining a dictionary containing multiple lists that hold all the primes found so far. Even if it instead kept yielding a list of all the primes so far (rather than the most recent prime) it would take less than twice the memory usage.
I'd say the flexibility to not need to know how big of a prime you'll need is the main draw.
- btilly 3y agoI obviously have a version without the memory issue. The programming flexibility is indeed the win. def primes (): yield 2 yield 3 f = {} n = 5 for p in primes(): if p == 2: continue p2 = p*p while n < p2: if n in f: double_p = f.pop(n) m = n + double_p while m in f: m += double_p f[m] = double_p else: yield n n += 2 f[n] = 2*p
- kmill 3y agoThis allocates a dictionary and the primes() generator for every single prime generated though, so it still has the memory issue, unless there's something I'm missing about how it works?
- btilly 3y agoPut a debugging statement in and you'll verify that the dictionary only contains primes up to the square root of the one just generated. To do that it recursively contains a second prime generator that only produces up to the square root. Which contains one that produces up to the fourth root. And so on until you get down to 3. The work and memory for those recursive generators is a rounding error compared to the initial prime generator. The work and memory saved by not keeping unnecessary primes is a significant win.
- kmill 3y agoOh, thanks for the explanation, I get how it works now. I hadn't seen this trick for an unbounded prime sieve before, and it's a nice idea.