Ist das ein guter Algorithmus zum Auflisten von Primzahlen?

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; 

Es ist eine Art One-Pass-Sieb von Eratosthenes Ansatz.

Ich habe Schleifen, gespeicherte Prozeduren und dergleichen sowie Pseudocode- und andere Sprachimplementierungen gesehen, aber es scheint mir, dass dieser einfache, mengenbasierte Ansatz, der aus der Definition von Primzahlen resultiert, ausreichen sollte.

Bitte beachten Sie, dass ich nicht auf Leistung oder Speicherverbrauch oder Optimierungen zu diesem Zeitpunkt, und ich habe es nicht mit größeren Zahlen getestet. Ich möchte nur den Algorithmus veröffentlichen und die Leute bestätigen lassen (oder herausfordern), dass das Ausschließen von zusammengesetzten Zahlen aus der Liste ausreicht.

Answer 1

Rekursive CTEs (rCTE) sind sehr selten die beste Lösung. Unten ist ein Ansatz, der eine Tally-Tabelle verwendet, ist es eine leicht gezwickt Version des Ansatzes ist, dass Hugo Kornelis hier gepostet: http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime-numbers.aspx

Lassen Sie uns die Tally-Tabelle zu der Lösung RCTE vergleichen:

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; 

und die Ergebnisse :

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. 

Wie Sie die tally-Tabelle Ansatz gegen 10.000 war 5mal schneller und auch jeder liest produziert nicht sehen kann, (eine Tonne produziert die RCTE!)

012.351.

Wenn Sie wirklich mit Primzahlen arbeiten, wäre der absolut schnellste Ansatz, sie in einer Tabelle zu speichern, so dass Sie sie nicht jedes Mal berechnen müssen, wenn Sie Primzahlen benötigen.