Bilangan prima dalam rentang tertentu

Baru-baru ini, saya diberi tugas untuk mencetak semua bilangan prima (1-100). Saya gagal secara drastis di sana. Kode Saya:

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

Meskipun saya berakhir tanpa menyelesaikannya, saya bertanya-tanya apakah itu layak untuk melakukan program-program seperti pada Database (SQL Server 2008 R2).

Jika ya, bagaimana itu bisa berakhir.

Sejauh ini cara tercepat dan termudah untuk mencetak "semua bilangan prima (1-100)" adalah dengan sepenuhnya merangkul kenyataan bahwa bilangan prima adalah seperangkat nilai yang diketahui, terbatas, dan tidak berubah ("diketahui" dan "terbatas" dalam suatu kisaran tertentu, tentu saja). Pada skala sekecil ini, mengapa membuang-buang CPU setiap waktu untuk menghitung banyak nilai yang telah dikenal untuk waktu yang sangat lama, dan hampir tidak memerlukan memori untuk disimpan?

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)

Tentu saja, jika Anda perlu menghitung bilangan prima antara 1 dan 100, berikut ini cukup efisien:

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

Kueri ini hanya menguji angka ganjil karena angka genap tidak akan menjadi yang utama. Ini juga spesifik untuk kisaran 1 - 100.

Sekarang, jika Anda memerlukan rentang dinamis (mirip dengan yang ditunjukkan pada contoh kode dalam pertanyaan), maka berikut ini adalah adaptasi dari kueri di atas yang masih agak efisien (dihitung rentang 1 - 100.000 - 9592 entri - hanya di bawah 1 detik):

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

Pengujian saya (menggunakan SET STATISTICS TIME, IO ON;) menunjukkan bahwa kueri ini berkinerja lebih baik daripada dua jawaban lain yang diberikan (sejauh ini):

RANGE: 1 - 100

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

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

RANGE: 1 - 10.000

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

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

RANGE: 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

RANGE: 99.900 - 100.000

CATATAN : Untuk menjalankan tes ini, saya harus memperbaiki bug dalam kode Dan - @startnumtidak dimasukkan ke dalam kueri sehingga selalu dimulai pada 1. Saya mengganti Dividend.num <= @endnumsaluran dengan Dividend.num BETWEEN @startnum AND @endnum.

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

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

RANGE: 1 - 100.000 (uji ulang parsial)

Setelah memperbaiki kueri Dan untuk pengujian 99.900 - 100.000, saya perhatikan bahwa tidak ada lagi bacaan logis yang terdaftar. Jadi saya menguji ulang kisaran ini dengan perbaikan yang masih diterapkan dan menemukan bahwa pembacaan logis hilang lagi dan waktunya sedikit lebih baik (dan ya, jumlah baris yang sama dikembalikan).

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

Dan                0             179,594            180,096

Cara sederhana namun tidak terlalu efisien untuk mengembalikan bilangan prima di kisaran 2-100 (1 tidak prima) adalah

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

Anda juga bisa berpotensi mewujudkan angka 2-100 dalam tabel dan menerapkan Saringan Eratosthenes melalui pembaruan atau penghapusan berulang.

Saya bertanya-tanya apakah layak untuk melakukan program-program semacam itu pada Database

Ya, itu layak tetapi saya tidak berpikir T-SQL adalah alat yang tepat untuk pekerjaan itu. Di bawah ini adalah contoh dari pendekatan berbasis set di T-SQL untuk masalah ini.

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

Kita dapat menulis kode di bawah ini dan berfungsi:

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

Di atas saya telah membuat Prosedur Tersimpan untuk mendapatkan bilangan prima.

Untuk mengetahui hasilnya, jalankan prosedur yang tersimpan:

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