Question :
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.
Answer :
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
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.
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
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
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