# Sieve of Eratosthenes

### From PostgreSQL wiki

Kudos to David Fetter for finally solving this one.

WITH RECURSIVE t0(m) AS ( VALUES(1000) ), t1(n) AS ( VALUES(2) UNION ALL SELECT n+1 FROM t1 WHERE n < (SELECT m FROM t0) ), t2 (n, i) AS ( SELECT 2*n, 2 FROM t1 WHERE 2*n <= (SELECT m FROM t0) UNION ALL ( WITH t3(k) AS ( SELECT MAX(i) OVER () + 1 FROM t2 ), t4(k) AS ( SELECT DISTINCT k FROM t3 ) SELECT k*n, k FROM t1 CROSS JOIN t4 WHERE k*k <= (SELECT m FROM t0) ) ) SELECT n FROM t1 EXCEPT SELECT n FROM t2 ORDER BY 1;