如何使用递归CTE实现指定范围内素数列表的查询

你可以直接在现有生成数字序列的基础上，通过NOT EXISTS子查询完成整除判断，不需要额外调整递归生成序列的逻辑，实现代码如下：

WITH RECURSIVE range(i) AS (
    SELECT 2 -- 素数最小为2，直接跳过1减少无效判断
    UNION ALL
    SELECT i + 1 FROM range LIMIT 100 -- 生成2~101的待判断数字序列
)
SELECT i AS prime FROM range r1
WHERE NOT EXISTS (
    SELECT 1 FROM range r2
    -- 校验是否存在2到当前数-1之间的整数可以整除它
    WHERE r2.i >= 2
      AND r2.i < r1.i
      AND MOD(r1.i, r2.i) = 0
);

逻辑说明 #

• 第一步调整数字序列的起始值为2，1不是素数无需参与判断
• 外层遍历每个待校验的数字r1.i，内层子查询遍历所有小于r1.i的整数做整除校验
• 只要存在任意一个数可以整除r1.i，NOT EXISTS就会返回false，对应数字会被过滤，剩下的结果就是素数列表

如果你需要完全用递归逻辑实现整除校验，不依赖子查询，也可以用下面的版本，完全符合你要求的遍历2到n-1所有数字做校验的逻辑：

WITH RECURSIVE candidates(i) AS (
    SELECT 2
    UNION ALL
    SELECT i + 1 FROM candidates LIMIT 100
),
prime_check(num, divisor, is_prime) AS (
    -- 初始化每个待校验数字的除数从2开始，默认标记为素数
    SELECT i, 2, 1 FROM candidates
    UNION ALL
    SELECT
        num,
        divisor + 1,
        -- 只要出现一次整除就标记为非素数
        CASE WHEN MOD(num, divisor) = 0 THEN 0 ELSE 1 END
    FROM prime_check
    -- 除数遍历到当前数-1就停止
    WHERE divisor < num - 1
)
SELECT DISTINCT num AS prime
FROM prime_check
GROUP BY num
-- 所有除数校验都通过才会保留
HAVING MIN(is_prime) = 1
ORDER BY num;

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