My favorite prime number generator

This is really elegant! To make the explanation more concrete, here's a snapshot of the algorithm's state (the dict D) after it has processed numbers up to 10 (inclusive):

    12: [3, 2]
    25: [5]
    49: [7]

So each prime up to 10 is present exactly once. When we process 12, we move 2 to the list for 14, and 3 to the list for 15.

The Sorenson paper linked in the post is also a great read, I remember reading it a couple of years ago and it is very clear. It adds many further optimizations on top of standard sieve of Eratosthenes (e.g. wheel factorization is a generalization of the idea of considering only numbers in {1, 5} mod 6, or {1, 7, 11, 13, 17, 19, 23, 29} mod 30, or …), and segmenting is what you need to do to avoid running out of memory.

The fastest such generator (using sieve-based methods) seems to be https://github.com/kimwalisch/primesieve — it implements all those optimizations and more.

However, if you just want the nth prime, it's even faster to compute π(n) by combinatorial/analytic methods, instead of a sieve: the same author has https://github.com/kimwalisch/primecount for that. (Try the ten-trillionth prime number.)

I enjoyed this, but I am a little stuck on how stuck the author is on yield. If one ends up creating a large list of prime numbers with this generator, why not just return a large list of prime numbers? The author clearly notes how optimizing Python code is "odd" when you can more easily switch languages, but languages like C/C++/Rust would not have pretty code because it does not have yield. It is obvious that returning an array of prime numbers is what one would do in C/C++/Rust.

I understand that not using yield would mean it is not strictly a "generator", but the spirit of this problem is generating the sequence of primes (unless I am missing something).

{(~T∊T∘.×T)/T←1↓⍳⍵}

> If one ends up creating a large list of prime numbers with this generator

But one does not always end up creating a large list of prime numbers, do they?

> why not just return a large list of prime numbers?

Because that requires upfront knowledge of the filtering factor or absence thereof.

A generator means you don't care, you generate an infinite sequence and the consumer is free to do whatever they want.

> It is obvious that returning an array of prime numbers is what one would do in C/C++/Rust.

It's certainly not obvious for Rust.

It's a bit of a convolution, but let's say we've got some iterator of unknown size and we want to have a prime each iteration. We can do the following in python, which saves us from having to pre-compute the primes _or_ know how long `some_iterator` is.

primes = gen_primes() for item, prime in zip(some_iterator, primes):