這是一個列舉素數的好算法嗎？

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生產一噸！）

如果您真的在使用素數，絕對最快的方法是將它們存儲在表中，因此每次需要素數時不需要計算它們。