Primzahlen in einem bestimmten Bereich

Kürzlich wurde mir die Aufgabe übertragen, alle Primzahlen (1-100) zu drucken. Ich habe dort drastisch versagt. Mein Code:

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

Obwohl ich es nicht abgeschlossen habe, frage ich mich, ob es möglich ist, solche Programme in einer Datenbank (SQL Server 2008 R2) auszuführen.

Wenn ja, wie kann es enden?

Der mit Abstand schnellste und einfachste Weg, "alle Primzahlen (1-100)" zu drucken, besteht darin, die Tatsache vollständig zu berücksichtigen, dass Primzahlen eine bekannte, endliche und unveränderliche Menge von Werten sind ("bekannt" und "endlich" innerhalb von a besondere Reichweite natürlich). Warum sollten Sie in diesem kleinen Maßstab jedes Mal CPU verschwenden, um eine Reihe von Werten zu berechnen, die seit langem bekannt sind, und kaum Speicherplatz zum Speichern benötigen?

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)

Wenn Sie die Primzahlen zwischen 1 und 100 berechnen müssen, ist Folgendes natürlich ziemlich effizient:

;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
                    );

Diese Abfrage testet nur ungerade Zahlen, da gerade Zahlen sowieso keine Primzahlen sind. Es ist auch spezifisch für den Bereich von 1 bis 100.

Wenn Sie nun einen Dynamikbereich benötigen (ähnlich wie im Beispielcode in der Frage gezeigt), ist das Folgende eine Anpassung der obigen Abfrage, die immer noch ziemlich effizient ist (sie hat den Bereich von 1 - 100.000 - 9592 berechnet Einträge - in knapp 1 Sekunde):

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
                    );

Meine Tests (mit SET STATISTICS TIME, IO ON;) zeigen, dass diese Abfrage eine bessere Leistung erbringt als die beiden anderen Antworten (bisher):

BEREICH: 1 - 100

Query      Logical Reads       CPU Milliseconds    Elapsed Milliseconds
-------    ----------------    ----------------    -----------------

Solomon      0                 0                   0
Dan        396                 0                   0
Martin     394                 0                   1

BEREICH: 1 - 10.000

Query      Logical Reads       CPU Milliseconds    Elapsed Milliseconds
-------    ----------------    ----------------    -----------------

Solomon        0                   47                170
Dan        77015                 2547               2559
Martin       n/a

BEREICH: 1 - 100.000

Query      Logical Reads       CPU Milliseconds    Elapsed Milliseconds
-------    ----------------    ----------------    -----------------

Solomon            0                 984                996
Dan        3,365,469             195,766            196,650
Martin           n/a

BEREICH: 99.900 - 100.000

HINWEIS : Um diesen Test auszuführen, musste ich einen Fehler in Dans Code beheben - @startnumwurde in der Abfrage nicht berücksichtigt, sodass er immer bei begann 1. Ich habe die Dividend.num <= @endnumLeitung durch ersetzt Dividend.num BETWEEN @startnum AND @endnum.

Query      Logical Reads       CPU Milliseconds    Elapsed Milliseconds
-------    ----------------    ----------------    -----------------

Solomon       0                   0                   1
Dan           0                 157                 158
Martin      n/a

BEREICH: 1 - 100.000 (teilweiser erneuter Test)

Nachdem ich Dans Abfrage für den 99.900 - 100.000 Test korrigiert hatte, stellte ich fest, dass keine logischen Lesevorgänge mehr aufgeführt waren. Also habe ich diesen Bereich erneut getestet, wobei der Fix noch angewendet wurde, und festgestellt, dass die logischen Lesevorgänge wieder weg waren und die Zeiten etwas besser waren (und ja, die gleiche Anzahl von Zeilen wurde zurückgegeben).

Query      Logical Reads       CPU Milliseconds    Elapsed Milliseconds
-------    ----------------    ----------------    -----------------

Dan                0             179,594            180,096

Eine einfache, aber nicht sehr effiziente Möglichkeit, die Primzahlen im Bereich von 2 bis 100 (1 ist keine Primzahl) zurückzugeben, wäre

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);

Sie können möglicherweise auch die Zahlen 2-100 in einer Tabelle materialisieren und das Sieb des Eratosthenes durch wiederholte Aktualisierungen oder Löschungen implementieren .

Ich frage mich, ob es möglich ist, solche Programme in der Datenbank auszuführen

Ja, das ist machbar, aber ich denke nicht, dass T-SQL das richtige Werkzeug für diesen Job ist. Unten finden Sie ein Beispiel für einen satzbasierten Ansatz in T-SQL für dieses Problem.

CREATE PROC dbo.PrintPrimeNumbers
    @startnum int,
    @endnum int
AS 
WITH 
     t4 AS (SELECT n FROM (VALUES(0),(0),(0),(0)) t(n))
    ,t256 AS (SELECT 0 AS n FROM t4 AS a CROSS JOIN t4 AS b CROSS JOIN t4 AS c CROSS JOIN t4 AS d)
    ,t16M AS (SELECT ROW_NUMBER() OVER (ORDER BY (a.n)) AS num FROM t256 AS a CROSS JOIN t256 AS b CROSS JOIN t256 AS c)
SELECT num
FROM t16M AS Dividend
WHERE
    Dividend.num <= @endnum
    AND NOT EXISTS(
        SELECT 1
        FROM t16M AS Divisor
        WHERE
            Divisor.num <= @endnum
            AND Divisor.num BETWEEN 2 AND SQRT(Dividend.num)
            AND Dividend.num % Divisor.num = 0
            AND Dividend.num <= @endnum
    );
GO
EXEC dbo.PrintPrimeNumbers 1, 100;
GO

Wir können den folgenden Code schreiben und es funktioniert:

CREATE procedure sp_PrimeNumber(@number int)
as 
begin
declare @i int
declare @j int
declare @isPrime int
set @isPrime=1
set @i=2
set @j=2
while(@i<=@number)
begin
    while(@j<=@number)
    begin
        if((@i<>@j) and (@i%@j=0))
        begin
            set @isPrime=0
            break
        end
        else
        begin
            set @j=@j+1
        end
    end
    if(@isPrime=1)
    begin
        SELECT @i
    end
    set @isPrime=1
    set @i=@i+1
    set @j=2
end
end

Oben habe ich eine gespeicherte Prozedur erstellt, um Primzahlen zu erhalten.

Führen Sie die gespeicherte Prozedur aus, um die Ergebnisse zu erfahren:

EXECUTE sp_PrimeNumber 100

DECLARE @UpperLimit INT, @LowerLimit INT

SET @UpperLimit = 500
SET @LowerLimit = 100

DECLARE @N INT, @P INT
DECLARE @Numbers TABLE (Number INT NULL)
DECLARE @Composite TABLE (Number INT NULL)

SET @P = @UpperLimit

IF (@LowerLimit > @UpperLimit OR @UpperLimit < 0 OR @LowerLimit < 0 )
    BEGIN
        PRINT 'Incorrect Range'
    END 
ELSE
    BEGIN
        WHILE @P > @LowerLimit
            BEGIN
                INSERT INTO @Numbers(Number) VALUES (@P)
                SET @N = 2
                WHILE @N <= @UpperLimit/2
                    BEGIN
                        IF ((@P%@N = 0 AND @P <> @N) OR (@P IN (0, 1)))
                            BEGIN
                                INSERT INTO @Composite(Number) VALUES (@P)
                                BREAK
                            END
                        SET @N = @N + 1
                    END
                SET @P = @P - 1
            END
        SELECT Number FROM @Numbers
        WHERE Number NOT IN (SELECT Number FROM @Composite)
        ORDER BY Number
        END