Implementation of Sieve of Eratosthenes by SQL(PostgreSQL)

sieve_of_eratosthenes.sql

CREATE OR REPLACE FUNCTION sieve_of_eratosthenes(int) RETURNS SETOF int AS $$
    WITH RECURSIVE
    --数列を用意
    t1(n) AS (
        SELECT generate_series(2, $1)
    ),
    t2 (n, i) AS (
        --初期化:2で割り切れない集合を作成
        SELECT
            n
            ,2
        FROM 
            t1
        WHERE 
            (n%2) <> 0
        --再起:再起集合内の最小値で割り切れる値を除いた集合を新たに再起集合とする
        UNION ALL(
            --再起集合をコピー（再起集合は再起部で一度しか呼び出せないため）
            WITH s1 (n) AS(
                SELECT
                    n
                FROM
                    t2
            )
            --再起集合内の最小値を取得
            ,s2 (k) AS(
                SELECT
                    min(n)
                FROM
                    s1
            )
            --最小値で割り切れる値を除外して集合を作成
            SELECT
                n
                ,k
            FROM
                s1,s2
            WHERE
                (n%k) <> 0
                AND k*k < $1 --√nで再起を終了
        )
    )
    --除数に用いた数は素数
    SELECT DISTINCT
        i AS n
    FROM
        t2
    UNION
    --最後に残った集合も素数
    SELECT
        n
    FROM
        t2
    WHERE
        i = (SELECT max(i) FROM t2)
    ORDER BY
        n
$$ LANGUAGE SQL IMMUTABLE STRICT;
SELECT sieve_of_eratosthenes(10000);