[xelxebar]

Eep. You're right. Evidently, I didn't even know what a sieve was in this context and wrote a search instead. You got me to do a bit of research. Actually, this discussion is exactly where I think APL shows one of it's strengths. It feels like a human communication tool more than any other PL I've mucked about with. The hard parts here are not language issues but fundamental understanding ones.

It's a tad tricky to carefully analyze the asymptotics of my above prime generator, since the search space of Without (~) shrinks on each iteration. I think Merten's theorem gives an estimate of e^-γ/log(p_i), which we need to sum for all primes up to N. Taking prime density 1/log(n) and integrating N/(log x)^2 over our range is O(N^2/log N), I think.

> Mutating a bit array in place is pretty important to classical sieve performance.

Challenge accepted:

    p⊣{x[⍵+n×⍳⌊N÷n←p⍪←x[⍵]]←0 ⋄ 1+⍣{(x⍪1)[⍵+1]≠0}⊢⍵}⍣{⍵=N-2}0⊣x p←(1↓1+⍳N)⍬

We just directly set roughly N/p items to 0 on each iteration—proper sieve semantics—which should give O(N log log N), unless I'm missing something.