10

Recently, I was given a task to print all the prime numbers (1-100). I failed drastically there. My 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

Though I ended up without completing it, I wonder is it feasible to do such programs on Database (SQL Server 2008 R2).

If yes, how it may end.

  • 2
    Not to take away from any of the answers given, but this is the best article I've seen on the topic: sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/… – Erik Darling Sep 10 '16 at 22:22
  • Is the goal to just do 1 - 100, or any range and 1 - 100 was just an example range? – Solomon Rutzky Sep 11 '16 at 17:46
  • In my question, it was 1 to 100. I would be good to get a generalistic approach, then a specific one. – ispostback Sep 11 '16 at 17:48
11

By far the quickest and easiest way to print "all the prime numbers (1-100)" is to fully embrace the fact that prime numbers are a known, finite, and unchanging set of values ("known" and "finite" within a particular range, of course). At this small of a scale, why waste CPU each time to calculate a bunch of values that have been known for a very long time, and take up hardly any memory to store?

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)

Of course, if you do need to calculate the prime numbers between 1 and 100, the following is fairly efficient:

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

This query only tests odd numbers as even numbers won't be prime anyway. It is also specific to the range of 1 - 100.

Now, if you need a dynamic range (similar to what is shown in the example code in the question), then the following is an adaptation of the query above that is still rather efficient (it calculated the range of 1 - 100,000 -- 9592 entries -- in just under 1 second):

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

My testing (using SET STATISTICS TIME, IO ON; ) shows that this query performs better than the other two answers given (so far):

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

NOTE: In order to run this test I had to fix a bug in Dan's code -- @startnum was not factored into the query so it always started at 1. I replaced the Dividend.num <= @endnum line with 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 (partial re-test)

After fixing Dan's query for the 99,900 - 100,000 test, I noticed that there were no more logical reads listed. So I retested this range with that fix still applied and found that the logical reads were again gone and the times were slightly better (and yes, the same number of rows were returned).

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

Dan                0             179,594            180,096
  • What is the purpose of ROW_NUMBER() OVER (ORDER BY (SELECT 1))? Would not ROW_NUMBER() OVER () be equivalent? – Lennart Jul 20 '18 at 15:05
  • Hi @Lennart .If you attempt to use OVER (), you will get the following error: The function 'ROW_NUMBER' must have an OVER clause with ORDER BY.. And, with ORDER BY, it can't be a constant, hence the subquery to return a constant. – Solomon Rutzky Jul 20 '18 at 15:56
  • 1
    Thanks, I was not aware of this limitation in sql server. Makes sense now – Lennart Jul 20 '18 at 15:58
  • Why if I use DECLARE @RangeStart INT = 999900, @RangeEnd INT = 1000000; it works but as soon as I set DECLARE @RangeStart INT = 9999999900, @RangeEnd INT = 10000000000; it says Msg 8115, Level 16, State 2, Line 1 Arithmetic overflow error converting expression to data type int. Msg 1014, Level 15, State 1, Line 5 A TOP or FETCH clause contains an invalid value.? – Francesco Mantovani Sep 21 '18 at 10:26
  • 1
    @FrancescoMantovani That error is saying that your values are outside of the range of INT. The max value that INT can hold is 2,147,483,647, which is smaller than your starting value of 9,999,999,900. You get that error even if you execute just the DECLARE. You can try changing the variable datatypes to be BIGINT and see how that goes. It is possible that other minor changes will be needed in order to support that. For datatype ranges, please see: int, bigint, smallint, and tinyint. – Solomon Rutzky Sep 21 '18 at 13:24
7

A simple but not very efficient way to return the prime numbers in the range 2-100 (1 is not prime) would be

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

You could also potentially materialise the numbers 2-100 in a table and implement the Sieve of Eratosthenes via repeated updates or deletes.

4

I wonder is it feasible to do such programs on Database

Yes, it is feasible but I don't think T-SQL is the right tool for the job. Below is an example of a set-based approach in T-SQL for this 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
0

We can write the below code and it works:

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

Above I have created a Stored Procedure to obtain prime numbers.

In order to know the results, execute the stored procedure:

EXECUTE sp_PrimeNumber 100
0
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.