基于递归SQL CTE的质数生成器优化实现问询

你给出的代码通过逐个判断模运算来筛选质数，确实存在冗余且扩展性差。下面提供两种无需手动编写所有模条件的递归CTE实现，完全基于SQL标准语法，不需要过程代码或扩展：

方法一：分阶段生成候选数+质数筛选 #

这种方式拆分两个递归CTE，一个负责生成候选数，另一个负责基于已找到的质数进行筛选，利用质数的因数必为质数的性质，只需要检查到候选数的平方根即可：

WITH RECURSIVE
-- 生成2到100的所有候选自然数（1不是质数，直接从2开始）
nums(n) AS (
    SELECT 2
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 100
),
-- 递归筛选质数：初始质数为2，后续每个候选数若不能被已找到的、不超过其平方根的质数整除，则为质数
primes(p, next_candidate) AS (
    SELECT n, n FROM nums WHERE n = 2
    UNION ALL
    SELECT 
        CASE WHEN NOT EXISTS (
            SELECT 1 FROM primes 
            WHERE p <= SQRT(n.n) AND n.n % p = 0
        ) THEN n.n ELSE NULL END,
        n.n
    FROM nums n
    JOIN primes ON n.n = primes.next_candidate + 1
    WHERE n.n <= 100
)
-- 过滤非质数的NULL值，得到最终质数列表
SELECT p AS prime FROM primes WHERE p IS NOT NULL;

逻辑说明 #

1. nums CTE生成所有待检查的候选数，范围可通过WHERE n < 100灵活调整；
2. primes CTE从第一个质数2开始，每次取下一个候选数，检查它是否能被已发现的质数（且不超过自身平方根）整除：
   • 若没有能整除的质数，说明该数是质数，保留数值；
   • 否则标记为NULL，后续过滤掉；
3. 最终只提取非NULL的结果，就是目标范围内的所有质数。

方法二：单递归CTE整合生成与筛选 #

如果想要更紧凑的写法，可以用单个递归CTE同时处理候选数生成和质数列表维护，通过字符串存储已找到的质数：

WITH RECURSIVE prime_checker(num, prime_list, is_prime) AS (
    -- 初始状态：从2开始，质数列表初始为'2'，第一个质数是2
    SELECT 2, CAST('2' AS TEXT), 2
    UNION ALL
    SELECT 
        num + 1,
        -- 若当前数是质数，将其追加到质数列表
        CASE WHEN NOT EXISTS (
            SELECT 1 FROM unnest(string_to_array(prime_list, ',')) AS p
            WHERE CAST(p AS INTEGER) <= SQRT(num + 1) AND (num + 1) % CAST(p AS INTEGER) = 0
        ) THEN prime_list || ',' || (num + 1) ELSE prime_list END,
        -- 判断当前数是否为质数
        CASE WHEN NOT EXISTS (
            SELECT 1 FROM unnest(string_to_array(prime_list, ',')) AS p
            WHERE CAST(p AS INTEGER) <= SQRT(num + 1) AND (num + 1) % CAST(p AS INTEGER) = 0
        ) THEN num + 1 ELSE NULL END
    FROM prime_checker
    WHERE num < 100
)
-- 提取所有有效质数
SELECT is_prime AS prime FROM prime_checker WHERE is_prime IS NOT NULL;

逻辑说明 #

1. 用prime_list字符串存储已找到的质数，每次新数生成时，拆分字符串得到所有已发现的质数；
2. 检查新数是否能被这些质数（不超过自身平方根）整除，若不能则判定为质数并加入列表；
3. 同样通过过滤NULL值得到最终质数结果。

这两种方法都无需手动编写所有模运算条件，扩展性极强——要生成更大范围的质数，只需要修改递归终止条件中的数值即可。

内容的提问来源于stack exchange，提问作者David542