Ward Pond's SQL Server blog

Ruminating on issues pertinent to the design and development of sound databases and processes under Microsoft SQL Server 2008, SQL Server 2005, and SQL Server 2000 (while reserving the right to vent about anything else that's on my mind)

Blogs

Database Programming: A Prime Number Contender From Down Under

  • Comments 6
  • Likes

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
Your comment has been posted.   Close
Thank you, your comment requires moderation so it may take a while to appear.   Close
Leave a Comment