这是一个列举素数的好算法吗？

Question

DECLARE @c int = 1000; 
DECLARE @numbers TABLE (n int NOT NULL PRIMARY KEY); 
DECLARE @products TABLE (p int NOT NULL PRIMARY KEY); 
DECLARE @primes TABLE (p int NOT NULL PRIMARY KEY); 

-- The 'composite exclusion' approach 

-- 1. list all n = 2, 3, 4, ... c 
WITH numbers AS 
(
    SELECT 2 AS n 
    UNION ALL 
    SELECT n + 1 FROM numbers 
    WHERE n <= @c - 1 
) 
INSERT INTO @numbers SELECT n FROM numbers OPTION(MAXRECURSION 0); 

-- 2. find all products n x n <= c 
WITH products AS 
(
    SELECT DISTINCT m.n * n.n AS p 
    FROM @numbers m LEFT OUTER JOIN 
      @numbers n ON 1 = 1 
    WHERE m.n * n.n <= @c 
) 
INSERT INTO @products SELECT p FROM products; 

-- 3. numbers with no matching products are not composite, i.e, they're prime numbers. 
INSERT INTO @primes 
SELECT n.n FROM @numbers n LEFT JOIN @products p ON n.n = p.p WHERE p.p IS NULL; 

这是一种通过Eratosthenes方法的Sieve。

我见过循环，存储过程等等，以及伪代码和其他语言实现，但在我看来，这种简单的基于集合的方法源于定义的素数应该就足够了。

请记住，我不关心性能或内存消耗或优化在这个时候，我没有测试它与更大的数字。我只想发布算法，并让人们确认（或挑战）从列表中排除复合数字就足够了。

Answer 1

递归CTE（rCTE）很少是最好的解决方案。下面是使用了提示表的方法，那就是雨果Kornelis这里贴的方法的略微调整了版本：http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime-numbers.aspx

让我们比较符合表解决rCTE解决方案：

SET STATISTICS TIME ON; 

PRINT 'tally table approach'+char(13)+char(10)+replicate('-',50); 
DECLARE @primes TABLE (p int NOT NULL PRIMARY KEY); 
DECLARE @limit bigint = 10000; 

WITH E(x) AS (SELECT * FROM (VALUES (1),(1),(1),(1),(1),(1),(1),(1),(1),(1)) t(x)), 
iTally(N) AS (SELECT TOP(@limit) ROW_NUMBER() OVER (ORDER BY (SELECT 1)) FROM E a, E b, E c, E d, E f) 
INSERT @primes 
SELECT  n1.N 
FROM  itally AS n1 
WHERE  n1.N > 1 
AND   n1.N < @Limit 
AND NOT EXISTS 
(SELECT * 
    FROM  itally AS n2 
    WHERE  n2.N < @limit 
    AND  n2.N BETWEEN 2 AND n1.N-1 
    AND  n1.n % n2.N = 0) 
--ORDER BY N 
GO 

PRINT 'rCTE approach'+char(13)+char(10)+replicate('-',50); 
DECLARE @c int = 10000; 
DECLARE @numbers TABLE (n int NOT NULL PRIMARY KEY); 
DECLARE @products TABLE (p int NOT NULL PRIMARY KEY); 
DECLARE @primes TABLE (p int NOT NULL PRIMARY KEY); 

WITH numbers AS 
(
    SELECT 2 AS n 
    UNION ALL 
    SELECT n + 1 FROM numbers 
    WHERE n <= @c - 1 
) 
INSERT INTO @numbers SELECT n FROM numbers OPTION(MAXRECURSION 0); 

-- 2. find all products n x n <= c 
WITH products AS 
(
    SELECT DISTINCT m.n * n.n AS p 
    FROM @numbers m LEFT OUTER JOIN 
      @numbers n ON 1 = 1 
    WHERE m.n * n.n <= @c 
) 
INSERT INTO @products SELECT p FROM products; 

-- 3. numbers with no matching products are not composite, i.e, they're prime numbers. 
INSERT INTO @primes 
SELECT n.n FROM @numbers n LEFT JOIN @products p ON n.n = p.p WHERE p.p IS NULL; 

SET STATISTICS TIME OFF; 

和结果：

tally table approach 
-------------------------------------------------- 

SQL Server Execution Times: 
    CPU time = 3042 ms, elapsed time = 3241 ms. 
SQL Server parse and compile time: 
    CPU time = 0 ms, elapsed time = 10 ms. 

rCTE approach 
-------------------------------------------------- 

SQL Server Execution Times: 
    CPU time = 14976 ms, elapsed time = 15757 ms. 

正如你所看到的，对10000理货表的做法是快5倍，也不会产生任何读取（在rCTE生产一吨！）

如果您真的在使用素数，绝对最快的方法是将它们存储在表中，因此每次需要素数时不需要计算它们。