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. p⊣{ω~n×1+⍳⌊N÷p⍪←n←ω↑⍨1⌊≢ω}⍣≡1↓1+⍳N⊣p←⍬
The algorithm is O(N log log N) as expected of a naive Eratosthenes implementation. You'll need ⎕IO←0 if you want to try it out.