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.
Best 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?
Of course, if you do need to calculate the prime numbers between 1 and 100, the following is fairly efficient:
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):
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
RANGE: 1 - 10,000
RANGE: 1 - 100,000
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 at1
. I replaced theDividend.num <= @endnum
line withDividend.num BETWEEN @startnum AND @endnum
.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).