埃拉托斯特尼筛法

有趣片段

埃拉托斯特尼筛法

适用于 PostgreSQL

>=8.4

用

SQL

依赖于

无

感谢 David Fetter 最终解决了这个问题。

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;