Sieve of Eratosthenes

Fun Snippets

Sieve of Eratosthenes

Works with PostgreSQL

>=8.4

Written in

SQL

Depends on

Nothing

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;