Database Programming: A Prime Number Contender From Down Under


Denis’ Prime Number Challenge just won’t die.  I think this topic has spurred more dialog than any other in this blog’s 15-month, 180-odd post history.  Just imagine if I could’ve harnessed this global outpouring of SQL skills for something with commercial potential.. J


Rob Farley has two posts on his blog on the topic (as well as a comment here) announcing his arrival at the party.  Here’s his syntax (with a slight tweak I’ll discuss in a moment):


create table rf_primesfound (num int)


go


truncate table rf_primesfound


go


 


DECLARE @BigLimit int;


SET @BigLimit = 1000000;


 


DECLARE @Limit int;


SET @Limit = 32;


DECLARE @OldLimit int;


SET @OldLimit = 32;


 


DECLARE @Start datetime, @End datetime;


SET @Start = CURRENT_TIMESTAMP;


 


insert into dbo.rf_primesfound (num)


select 2 union all


select 3 union all


select 5 union all


select 7 union all


select 11 union all


select 13 union all


select 17 union all


select 19 union all


select 23 union all


select 29 union all


select 31;


 


while @limit < @BigLimit


begin


select @Oldlimit = @limit, @limit = @limit * @limit;


if @limit > @BigLimit set @limit = @BigLimit;


 


insert into dbo.rf_primesfound


select p.num


from dbo.nums n1


join


dbo.rf_primesfound f


on n1.num between 2 and @limit / f.num


right join


dbo.nums p


on p.num = f.num * n1.num


where f.num is null


and p.num > @Oldlimit


and p.num <= @limit;


 


end


 


SET @End = CURRENT_TIMESTAMP


 


SELECT @Start AS Start_time, @End AS End_time,


DATEDIFF(ms, @Start, @End) AS Duration,


COUNT(*) AS Primes_found, @Limit AS Limit


FROM dbo.rf_primesfound


 


select * from dbo.rf_primesfound


This is the same code in Rob’s second post, except that I’ve added DDL (and a TRUNCATE) for rf_primesfound, and I moved the initial population of the “low-hanging fruit” inside of the timed portion of the code (nobody rides for free J).


This code seems to run about 800-1200ms slower on my laptop than the current leader (my tweak of Hugo’s code).  However, I think Rob’s technique is noteworthy for its set-based orientation, and for the fact that he’s inserting the prime numbers into his table rather than deleting the composites as Hugo did.


Thanks for jumping into the fray, Rob, with a worthy contender!


We’ve got at least two continents represented in the Challenge now..  keep those comments and blog posts coming..


    -wp

Comments (6)

  1. Anonymous says:

    I’m in western Vermont until Wednesday morning, totally off the grid except for a 56K dialup connection

  2. Anonymous says:

    No less a figure than Louis Davidson has weighed in on the Prime Number Challenge . I left a comment

  3. Rob Farley says:

    Ward – how do you justify having the ‘initial fill of sieve’ in your tweak of Hugo’s? If you pull that stuff out (as per my first post), it takes much longer.

    Rob (new SQL MVP, by the way!)

  4. Rob Farley says:

    Like… just populate both with ‘2’, and see how they go. My first one (without the looping) seems to do better in that scenario, but I prefer the algorithm of the second one.

    Rob