Use The Sieve of Eratosthenes To Find All PrimeNumbers Below 1 Million

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer. It was created by Eratosthenes, an ancient Greek mathematician. Wheel factorization is often applied on the list of integers to be checked for primality, before Sieve of Eratosthenes is used, to increase the speed.


Algorithm
Write a list of numbers from 2 to the largest number you want to test for primality. Call this List A. (This is the list of squares on the left-hand-side of the picture.)
Write the number 2, the first prime number, in another list for primes found. Call this List B. (This is the list on the right-hand-side of the picture.)
Strike off 2 and all multiples of 2 from List A.
The first remaining number in the list is a prime number. Write this number into List B.
Strike off this number and all multiples of this number from List A. The crossing-off of multiples can be started at the square of the number, as lower multiples have already been crossed out in previous steps.
Repeat steps 4 through 6 until no more numbers are left in List A.

Read more on Wikipedia


So here is the SQL Version, it runs in 7 seconds on my machine when I run it a
second time, first run is 16 seconds

SET NOCOUNT ON


DECLARE @i INT

-- Create a 10-digit table
DECLARE @D TABLE (N INT)
INSERT INTO @D (N) 
SELECT 0 UNION ALL 
SELECT 1 UNION ALL 
SELECT 2 UNION ALL 
SELECT 3 UNION ALL 
SELECT 4

INSERT INTO @D (N) 
SELECT N+5 FROM @D

-- build a small sieve table between 2 and 1000
DECLARE @T TABLE (N INT)
INSERT INTO @T( N )
SELECT 1+A.N+10*(B.N+10*C.N)
FROM @D A, @D B, @D C

DELETE FROM @T WHERE N = 1

SET @I = 2
WHILE @I <= SQRT(1000)
BEGIN
    DELETE FROM @T WHERE N % @I = 0 AND N > @I
    SET @I = @I + 1
END

-- Create large table between 1001 and 1000000
SELECT A+10*(B+10*(C+10*(D+10*(E+ 10*F)))) AS N
INTO #P
FROM
(    SELECT A.N AS A, B.N AS B, C.N AS C, D.N AS D, E.N AS E, F.N AS F
    FROM @D A, @D B, @D C, @D D, @D E, @D F
    WHERE A.N in (1, 3, 7, 9)  -- Not divisible by 2 or 5
) blah
WHERE (A+B+C+D+E+F) % 3 <> 0 -- Or 3
    AND (A+3*B+2*C-D-3*E-2*F) % 7 <> 0 -- Or 7
    AND (B-A+D-C+F-E) % 11 <> 0 -- Or 11
    AND D|E|F <> 0 -- Don't include the first 1000 numbers, 
--we already have these in the small sieve table
UNION ALL SELECT 1000000

-- sieve the big table with smaller one
SELECT @I = 2 
WHILE @I IS NOT NULL
BEGIN
    DELETE FROM #P WHERE N% @I = 0
    SELECT @I = MIN(N) FROM @T WHERE N > @I
END

-- add primes up to 1000
INSERT INTO #P SELECT N FROM @T

-- Here are the results
--78498 rows
SELECT  * FROM #P ORDER BY 1

drop table #P
go