Database Programming: Denis’ Prime Number Challenge: A New Leader

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


DECLARE @Limit int

SET     @Limit = 1000000


— Initial fill of sieve;

— filter out low hanging fruit right from the start.

INSERT  INTO dbo.Primes (Prime)


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


  — 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)




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


Comments (8)

  1. Anonymous says:

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

  2. Anonymous says:

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

  3. Anonymous says:

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


  4. Anonymous says:

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

  5. Anonymous says:

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

  6. Anonymous says:

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

  7. Omnibuzz says:

    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 🙂