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
