这是列出质数的好算法吗? [英] Is this a good algorithm for listing prime numbers?
问题描述
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筛网筛分法。
It's kind of a one pass Sieve of Eratosthenes approach.
我已经看过循环,存储过程之类的东西,以及伪代码和其他语言的实现,但是在我看来,这种基于素数的简单,基于集合的方法就足够了
I've seen loops, stored procedures and the like, as well as pseudo-code and other language implementations, but it seems to me that this simple, set-based approach stemming from the definition of prime numbers should suffice.
请记住,我目前不关心性能,内存消耗或优化,也没有对它进行较大的测试。我只想发布算法,让人们确认(或挑战)从列表中排除复合数字就足够了。
Please bear in mind I'm not concerned with performance or memory consumption or optimizations at this time, and I have not tested it with larger numbers. I just want to publish the algorithm and have people confirm (or challenge) that excluding composite numbers from the list is enough.
推荐答案
递归CTE(rCTE)很少是性能最好的解决方案。以下是使用计数表的方法,它是Hugo Kornelis在此处发布的方法的略微调整版本:> https://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time /
Recursive CTEs (rCTE) are very rarely the best performing solution. Below is an approach that uses a tally table, it's a slightly tweaked version of the approach that Hugo Kornelis posted here: https://sqlserverfast.com/blog/hugo/2006/09/the-prime-number-challenge-great-waste-of-time/
让我们将理货表解决方案与rCTE解决方案进行比较:
Let's compare the tally table solution to the rCTE solution:
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.
如您所见,针对10,000的计数表方法快了5倍,并且也不会产生任何读取(rCTE会产生一吨!)
As you can see, the tally table approach against 10,000 was 5 times faster and also doesn't produce any reads (the rCTE produces a ton!)
如果您真的在使用质数,则绝对最快的方法是将它们存储在表中,这样就不会每次需要质数时都需要计算它们。
If you are really working with prime numbers the absolute fastest approach would be to store them in a table so you don't need to calculate them each time you need prime numbers.
这篇关于这是列出质数的好算法吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!