Well, folks, there’s a new sheriff in town.. this is a continuation of a conversation here and here.

I’ve tweaked Hugo’s syntax to further filter the initial seive population (similar to the pre-filtering present in the discredited tangent). Where’s Hugo’s syntax took 8 seconds on my laptop and Denis’ took 6 seconds, this version takes under 3 seconds!

I’m going to let the discredited version run overnight.. hopefully somebody can do even better (although from two days down to three seconds is pretty cool; thanks, Hugo!).

Here’s the current leader (note that this version is also tweaked slightly to reflect the schema for my number source):

DECLARE @Start datetime, @End datetime

SET @Start = CURRENT_TIMESTAMP

DECLARE @Limit int

SET @Limit = 1000000

— Initial fill of sieve;

— filter out low hanging fruit right from the start.

INSERT INTO dbo.Primes (Prime)

SELECT Id

FROM dbo.SetBuilder

WHERE (Id % 2 <> 0 OR Id = 2)

AND (Id % 3 <> 0 OR Id = 3)

AND (Id % 5 <> 0 OR Id = 5)

AND (Id % 7 <> 0 OR Id = 7)

AND (Id % 11 <> 0 OR Id = 11)

AND (Id % 13 <> 0 OR Id = 13)

AND (Id % 17 <> 0 OR Id = 17)

AND (Id % 19 <> 0 OR Id = 19)

AND (Id % 23 <> 0 OR Id = 23)

AND (Id % 29 <> 0 OR Id = 29)

AND (Id % 31 <> 0 OR Id = 31)

AND Id <> 1

AND Id <= @Limit

— Set @Last to 31, since multiples of 31 and all primes lower have already been processed

DECLARE @First int, @Last int

SET @Last = 31

WHILE @Last <= SQRT(@Limit) + 1

BEGIN

— Find next prime as start of next range

SET @First =

(SELECT TOP (1) Prime

FROM dbo.Primes

WHERE Prime >= @Last + 1

ORDER BY Prime)

— Range to process ends at square of starting point

SET @Last = @First * @First

DELETE FROM dbo.Primes

WHERE Prime IN (SELECT n.Id * p.Prime

FROM dbo.Primes AS p

INNER JOIN dbo.SetBuilder AS n

ON n.Id >= p.Prime

AND n.Id <= @Limit / p.Prime

WHERE p.Prime >= @First

AND p.Prime < @Last)

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

Well, Denis and Hugo, what have you got? J

-wp

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

Great post, explained really well and I could really understand. Thank you.

It’s never too late to chime in, Omni, and thanks for your kind words!

-wp

Denis’ Prime Number Challenge just won’t die.&nbsp; I think this topic has spurred more dialog than any&nbsp;other…

Our blogging site is going to go dark in an hour or so for a software upgrade, so I won’t be able to…

Oh no, you may be thinking, he has gone off the deep end. Preparing for his talk on normalization…

I’ve jumped in…

http://robfarley.blogspot.com/2006/09/primes.html

http://robfarley.blogspot.com/2006/09/more-on-primes.html

Let me know what you think.

Hi all,

Pardon me if its too late a comment. Just wanted to tell that it was a wonderful implementation. Enjoyed reading through the posts. Nothing much to tweak from my side, though I thought hard and realised that I am not even in the league ðŸ™‚

-Omni