如何在SQLite中合并子查询结果并实现素数筛？

要解决SQLite中无法合并子查询倍数结果的问题，可以利用递归CTE的UNION ALL特性来累积生成所有合数，再通过自然数集合减去合数集合得到素数。以下是具体实现：

完整SQL代码 #

WITH RECURSIVE
-- 生成2到目标上限（此处为100）的自然数候选集
nums(n) AS (
  SELECT 2
  UNION ALL
  SELECT n + 1 FROM nums WHERE n < 100
),
-- 递归生成所有合数：通过UNION ALL累积每个素数的倍数
composites(n) AS (
  -- 初始步骤：生成第一个素数2的所有倍数（从4开始，避免包含素数本身）
  SELECT 2 * k.n FROM nums k WHERE 2 * k.n <= 100 AND k.n >= 2
  UNION ALL
  -- 递归步骤：找到下一个未被标记为合数的最小素数p，生成其所有倍数
  SELECT p.n * k.n
  FROM nums k,
       (SELECT MIN(n) AS n FROM nums WHERE n NOT IN composites AND n > (SELECT MAX(n) FROM composites)) p
  WHERE p.n * k.n <= 100 AND k.n >= p.n
)
-- 素数 = 自然数候选集 - 合数集合（去重避免重复的合数）
SELECT n FROM nums EXCEPT SELECT DISTINCT n FROM composites;

代码解释 #

1. nums CTE：生成从2到目标上限的连续自然数，作为素数的候选集合。
2. composites CTE：
   • 初始部分：先生成素数2的所有倍数（从2*2=4开始），确保不包含素数本身。
   • 递归部分：每次找到下一个未被筛掉的最小数p（即新的素数），然后生成p的所有倍数（从p*p开始，更小的倍数已被之前的素数筛除），并通过UNION ALL将这些倍数累积到合数集合中。
3. 最终查询：用自然数候选集减去去重后的合数集合，得到所有素数。

这种方式利用递归CTE的UNION ALL特性，完美解决了子查询结果无法合并的问题——每次递归都会将新生成的倍数集合合并到之前的结果中，而非仅返回单个值。

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