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;
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
while @limit < @BigLimit
select @Oldlimit = @limit, @limit = @limit * @limit;
if @limit > @BigLimit set @limit = @BigLimit;
insert into dbo.rf_primesfound
from dbo.nums n1
on n1.num between 2 and @limit / f.num
on p.num = f.num * n1.num
where f.num is null
and p.num > @Oldlimit
and p.num <= @limit;
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
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..
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!)
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.
PingBack from http://blogs.technet.com/wardpond/archive/2006/10/03/Database-Programming_3A00_-Prime-Number-Methodology.aspx
PingBack from http://blogs.technet.com/wardpond/archive/2006/10/03/Welcome-To-My-Bloo_2100_--I_2700_m-Afraid-I-Must-Be-Going-For-Awhile_2E002E00_.aspx
I'm in western Vermont until Wednesday morning, totally off the grid except for a 56K dialup connection
No less a figure than Louis Davidson has weighed in on the Prime Number Challenge . I left a comment