isp*_*ack 10 sql-server t-sql sql-server-2008-r2
最近，我接到了打印所有质数（1-100）的任务。我在那里彻底失败了。我的代码：
Create Procedure PrintPrimeNumbers
@startnum int,
@endnum int
AS
BEGIN
Declare @a INT;
Declare @i INT = 1
(
Select a = @startnum / 2;
WHILE @i<@a
BEGIN
@startnum%(@a-@i)
i=i+1;
)
END
虽然我最终没有完成它，但我想知道在数据库（SQL Server 2008 R2）上做这样的程序是否可行。
如果是，它会如何结束。
Sol*_*zky 11
到目前为止，打印“所有质数 (1-100)”的最快和最简单的方法是完全接受这样一个事实，即质数是一组已知的、有限的和不变的值（“已知”和“有限”在一个特定范围，当然）。在这么小的规模下，为什么每次都浪费CPU来计算一堆已知很长时间的值，并且几乎不占用任何内存来存储？
SELECT tmp.[Prime]
FROM (VALUES (2), (3), (5), (7), (11), (13),
(17), (19), (23), (29), (31), (37), (41),
(43), (47), (53), (59), (61), (67), (71),
(73), (79), (83), (89), (97)) tmp(Prime)
当然，如果您确实需要计算 1 到 100 之间的素数，以下方法相当有效：
;WITH base AS
(
SELECT tmp.dummy, ROW_NUMBER() OVER (ORDER BY (SELECT 1)) AS [num]
FROM (VALUES (0), (0), (0), (0), (0), (0), (0)) tmp(dummy)
), nums AS
(
SELECT (ROW_NUMBER() OVER (ORDER BY (SELECT 1)) * 2) + 1 AS [num]
FROM base b1
CROSS JOIN base b2
), divs AS
(
SELECT [num]
FROM base b3
WHERE b3.[num] > 4
AND b3.[num] % 2 <> 0
AND b3.[num] % 3 <> 0
)
SELECT given.[num] AS [Prime]
FROM (VALUES (2), (3)) given(num)
UNION ALL
SELECT n.[num] AS [Prime]
FROM nums n
WHERE n.[num] % 3 <> 0
AND NOT EXISTS (SELECT *
FROM divs d
WHERE d.[num] <> n.[num]
AND n.[num] % d.[num] = 0
);
这个查询只测试奇数，因为偶数无论如何都不会是素数。它也特定于 1 - 100 的范围。
现在，如果您需要一个动态范围（类似于问题中的示例代码中显示的内容），那么以下是上述查询的改编版，它仍然相当有效（它计算了 1 - 100,000 -- 9592 的范围条目 - 在不到 1 秒内）：
DECLARE @RangeStart INT = 1,
@RangeEnd INT = 100000;
DECLARE @HowMany INT = CEILING((@RangeEnd - @RangeStart + 1) / 2.0);
;WITH frst AS
(
SELECT tmp.thing1
FROM (VALUES (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) tmp(thing1)
), scnd AS
(
SELECT 0 AS [thing2]
FROM frst t1
CROSS JOIN frst t2
CROSS JOIN frst t3
), base AS
(
SELECT TOP( CONVERT( INT, CEILING(SQRT(@RangeEnd)) ) )
ROW_NUMBER() OVER (ORDER BY (SELECT 1)) AS [num]
FROM scnd s1
CROSS JOIN scnd s2
), nums AS
(
SELECT TOP (@HowMany)
(ROW_NUMBER() OVER (ORDER BY (SELECT 1)) * 2) +
(@RangeStart - 1 - (@RangeStart%2)) AS [num]
FROM base b1
CROSS JOIN base b2
), divs AS
(
SELECT [num]
FROM base b3
WHERE b3.[num] > 4
AND b3.[num] % 2 <> 0
AND b3.[num] % 3 <> 0
)
SELECT given.[num] AS [Prime]
FROM (VALUES (2), (3)) given(num)
WHERE given.[num] >= @RangeStart
UNION ALL
SELECT n.[num] AS [Prime]
FROM nums n
WHERE n.[num] BETWEEN 5 AND @RangeEnd
AND n.[num] % 3 <> 0
AND NOT EXISTS (SELECT *
FROM divs d
WHERE d.[num] <> n.[num]
AND n.[num] % d.[num] = 0
);
我的测试（使用SET STATISTICS TIME, IO ON;）表明此查询的性能优于给出的其他两个答案（到目前为止）：
范围：1 - 100
SELECT tmp.[Prime]
FROM (VALUES (2), (3), (5), (7), (11), (13),
(17), (19), (23), (29), (31), (37), (41),
(43), (47), (53), (59), (61), (67), (71),
(73), (79), (83), (89), (97)) tmp(Prime)
范围：1 - 10,000
;WITH base AS
(
SELECT tmp.dummy, ROW_NUMBER() OVER (ORDER BY (SELECT 1)) AS [num]
FROM (VALUES (0), (0), (0), (0), (0), (0), (0)) tmp(dummy)
), nums AS
(
SELECT (ROW_NUMBER() OVER (ORDER BY (SELECT 1)) * 2) + 1 AS [num]
FROM base b1
CROSS JOIN base b2
), divs AS
(
SELECT [num]
FROM base b3
WHERE b3.[num] > 4
AND b3.[num] % 2 <> 0
AND b3.[num] % 3 <> 0
)
SELECT given.[num] AS [Prime]
FROM (VALUES (2), (3)) given(num)
UNION ALL
SELECT n.[num] AS [Prime]
FROM nums n
WHERE n.[num] % 3 <> 0
AND NOT EXISTS (SELECT *
FROM divs d
WHERE d.[num] <> n.[num]
AND n.[num] % d.[num] = 0
);
范围：1 - 100,000
DECLARE @RangeStart INT = 1,
@RangeEnd INT = 100000;
DECLARE @HowMany INT = CEILING((@RangeEnd - @RangeStart + 1) / 2.0);
;WITH frst AS
(
SELECT tmp.thing1
FROM (VALUES (0), (0), (0), (0), (0), (0), (0), (0), (0), (0)) tmp(thing1)
), scnd AS
(
SELECT 0 AS [thing2]
FROM frst t1
CROSS JOIN frst t2
CROSS JOIN frst t3
), base AS
(
SELECT TOP( CONVERT( INT, CEILING(SQRT(@RangeEnd)) ) )
ROW_NUMBER() OVER (ORDER BY (SELECT 1)) AS [num]
FROM scnd s1
CROSS JOIN scnd s2
), nums AS
(
SELECT TOP (@HowMany)
(ROW_NUMBER() OVER (ORDER BY (SELECT 1)) * 2) +
(@RangeStart - 1 - (@RangeStart%2)) AS [num]
FROM base b1
CROSS JOIN base b2
), divs AS
(
SELECT [num]
FROM base b3
WHERE b3.[num] > 4
AND b3.[num] % 2 <> 0
AND b3.[num] % 3 <> 0
)
SELECT given.[num] AS [Prime]
FROM (VALUES (2), (3)) given(num)
WHERE given.[num] >= @RangeStart
UNION ALL
SELECT n.[num] AS [Prime]
FROM nums n
WHERE n.[num] BETWEEN 5 AND @RangeEnd
AND n.[num] % 3 <> 0
AND NOT EXISTS (SELECT *
FROM divs d
WHERE d.[num] <> n.[num]
AND n.[num] % d.[num] = 0
);
范围：99,900 - 100,000
注意：为了运行这个测试，我必须修复 Dan 代码中的一个错误——@startnum没有考虑到查询中，所以它总是从1. 我Dividend.num <= @endnum用Dividend.num BETWEEN @startnum AND @endnum.
Query Logical Reads CPU Milliseconds Elapsed Milliseconds
------- ---------------- ---------------- -----------------
Solomon 0 0 0
Dan 396 0 0
Martin 394 0 1
范围：1 - 100,000（部分重新测试）
在修复 Dan 对 99,900 - 100,000 测试的查询之后，我注意到没有列出更多的逻辑读取。所以我在仍然应用该修复程序的情况下重新测试了这个范围，发现逻辑读取再次消失，时间稍微好一点（是的，返回了相同数量的行）。
Query Logical Reads CPU Milliseconds Elapsed Milliseconds
------- ---------------- ---------------- -----------------
Solomon 0 47 170
Dan 77015 2547 2559
Martin n/a
返回 2-100 范围内的素数（1 不是素数）的一种简单但不是很有效的方法是
WITH Ten AS (SELECT * FROM (VALUES(0),(1),(2),(3),(4),(5),(6),(7),(8),(9)) V(N)),
Hundred(N) AS (SELECT T1.N * 10 + T2.N + 1 FROM Ten T1, Ten T2)
SELECT H1.N
FROM Hundred H1
WHERE H1.N > 1
AND NOT EXISTS(SELECT *
FROM Hundred H2
WHERE H2.N > 1
AND H1.N > H2.N
AND H1.N % H2.N = 0);
您还可以潜在地在表中实现数字 2-100，并通过重复更新或删除来实现Eratosthenes的筛选。