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)


truncate table rf_primesfound



DECLARE @BigLimit int;

SET @BigLimit = 1000000;


DECLARE @Limit int;

SET @Limit = 32;

DECLARE @OldLimit int;

SET @OldLimit = 32;


DECLARE @Start datetime, @End datetime;



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


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

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


insert into dbo.rf_primesfound

select p.num

from dbo.nums n1


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;






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..


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.


Skip to main content