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)
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
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)
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
Well, Denis and Hugo, what have you got? J
Our blogging site is going to go dark in an hour or so for a software upgrade, so I won't be able to...
I've jumped in...
Let me know what you think.
Denis' Prime Number Challenge just won't die.&nbsp; I think this topic has spurred more dialog than any&nbsp;other...
Oh no, you may be thinking, he has gone off the deep end. Preparing for his talk on normalization...
No less a figure than Louis Davidson has weighed in on the Prime Number Challenge . I left a comment
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 :)
It's never too late to chime in, Omni, and thanks for your kind words!
Great post, explained really well and I could really understand. Thank you.