I have been thinking about this topic in the back of my brain since I read the post this morning.

The initial attempt was good for a first attempt but the brute force method would not be best. By definition, the only values that we need to worry about are prime numbers for the check, since all other values would be divisible by these.

Using a Temp Table to store the primes, we could optimize as such:

(To get meaningful results, I increased the search to 10,000. The original algorithm took 170 seconds on an old test box. This optimized routine took 2 seconds. 100,000 numbers took 112 seconds)

DECLARE

@max-2 INT, -- Max number for prime search

@i INT, -- Counter for possible candidates

@count INT , -- row count of matches

@TimeStart DateTime , -- Time execution start

SET NOCOUNT ON

-- Create Temp Table for storing results

Create Table #Primes(PrimeNumber Int Not Null)

-- Initialize variables

SET @TimeStart = GetDate()

SET @max-2 = 10000

SET @count = 0

SET @i = 2

WHILE (@i <= @max-2)

BEGIN

SET @count = (SELECT COUNT(*) FROM #Primes WHERE (@i % PrimeNumber) = 0 )

If @count = 0

INSERT INTO #Primes(PrimeNumber) Values(@i)

SET @i = @i + 1

END

-- Output the results

SELECT * FROM #primes

-- output execution in seconds

print DateDiff(ss, GetDate(), @TimeEnd)

DROP TABLE #Primes