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