Hi Jeff,

Here's some code so you can run it yourself. I'll add some run results in the next post.

--Inputs
DECLARE @MaxNumber INT
SET @MaxNumber = 5000000

--Preparation
SET NOCOUNT ON
DECLARE @Time DATETIME
SELECT @Time = GETDATE()

--Preparation - Numbers table
DECLARE @SqrtMaxNumber INT
SET @SqrtMaxNumber = SQRT(@MaxNumber)
SET ROWCOUNT @SqrtMaxNumber
CREATE TABLE #Numbers (i BIGINT IDENTITY(1, 1) PRIMARY KEY CLUSTERED, j BIGINT, x bit)
INSERT INTO #Numbers (x) SELECT NULL FROM syscomments c1, syscomments c2, syscomments c3, syscomments c4
SET ROWCOUNT 0
UPDATE #Numbers SET j = i*i
PRINT 'Checkpoint A: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'

--Preparation - Put candidate primes into a Primes table
-- (integers which have an odd number of representations by certain quadratic forms)
CREATE TABLE #Primes (i BIGINT PRIMARY KEY CLUSTERED)
INSERT #Primes
SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT k FROM (
    SELECT k FROM (SELECT 4 * a.j + b.j AS k FROM #Numbers a, #Numbers b) c WHERE k <= @MaxNumber AND k % 12 IN (1, 5)
    UNION ALL
    SELECT k from (select 3 * a.j + b.j AS k FROM #Numbers a, #Numbers b) c WHERE k <= @MaxNumber AND k % 12 = 7
    UNION ALL
    SELECT k from (select 3 * a.j - b.j AS k FROM #Numbers a INNER JOIN #Numbers b ON a.i > b.i) c WHERE k <= @MaxNumber AND k % 12 = 11
) d GROUP BY k HAVING COUNT(*) IN (1, 3)
PRINT 'Checkpoint B: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'

--Calculation - Eliminate composites by sieving
DECLARE @i BIGINT
SET @i = 5
WHILE @i * @i < @MaxNumber
BEGIN
    DELETE #Primes WHERE i > @i and i % @i = 0
    SELECT @i = min(i) FROM #Primes WHERE i > @i
    PRINT @i
END

--Show results
PRINT 'Finish: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'
SELECT COUNT(*) AS 'Number of primes', MAX(i) AS 'Max prime', AVG(i) AS 'Average of primes' FROM #Primes
SELECT * FROM #Primes ORDER BY i

--Tidy up
DROP TABLE #Primes
DROP TABLE #Numbers

UNION ALL SELECT 100000000, 140, 466970, 1089933, 5761455, 99999989, 48461680

Good stuff Ryan!

Did you compare the runtime against any of the other code posted on this thread?

I have tested my code against Ryan's code on SQL Server 2000 and it seems to be equally fast (with the same output).
If the Numbers table is preconstructed, I guess my code is faster (because I need a larger Numbers table). On the other hand, if I am forced to use bigints (as Ryan does), my code will
be a bit slower.

I have used the following in my test:

/*************** MY CODE ******************/

set nocount on
go

declare @time datetime
select @time = getdate()

DECLARE @MaxNumber INT
SET @MaxNumber = 5000000

SET ROWCOUNT @MaxNumber

select identity(int, 1, 1) as Number into #Numbers
from syscomments c1 cross join syscomments c2 cross join syscomments c3

SET ROWCOUNT 0

alter table #Numbers add constraint PK_Numbers primary key clustered (Number)

create table #Primes(prime int primary key)

declare @i int, @limit int
set @i = 1
while @i*@i < @MaxNumber
begin
  set @limit = (@i+1)*(@i+1)
  if (@i+1)*(@i+1) > @MaxNumber
    set @limit = @MaxNumber + 1

  insert into #Primes
  select n.Number
  from #Numbers n
  where
  n.Number < @limit and n.Number > @i*@i
  and not exists
  (select * from #Primes p where p.prime < @i + 1 and n.Number % p.prime = 0)

  set @i = @i + 1
end

--select * from #Primes

PRINT 'Finish: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'
SELECT COUNT(*) AS 'Number of primes', MAX(prime) AS 'Max prime' FROM #Primes

drop table #Primes
go

drop table #Numbers
go

/******** RYAN'S CODE************************/

--Inputs
DECLARE @MaxNumber INT
SET @MaxNumber = 5000000

--Preparation
SET NOCOUNT ON
DECLARE @Time DATETIME
SELECT @Time = GETDATE()

--Preparation - Numbers table
DECLARE @SqrtMaxNumber INT
SET @SqrtMaxNumber = SQRT(@MaxNumber)
SET ROWCOUNT @SqrtMaxNumber
CREATE TABLE #Numbers (i BIGINT IDENTITY(1, 1) PRIMARY KEY CLUSTERED, j BIGINT, x bit)
INSERT INTO #Numbers (x) SELECT NULL FROM syscomments c1 CROSS JOIN syscomments c2
SET ROWCOUNT 0
UPDATE #Numbers SET j = i*i
PRINT 'Checkpoint A: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'

--Preparation - Put candidate primes into a Primes table
-- (integers which have an odd number of representations by certain quadratic forms)
CREATE TABLE #Primes (i BIGINT PRIMARY KEY CLUSTERED)
INSERT #Primes
SELECT 2 UNION ALL SELECT 3 UNION ALL
SELECT k FROM (
    SELECT k FROM (SELECT 4 * a.j + b.j AS k FROM #Numbers a, #Numbers b) c WHERE k <= @MaxNumber AND k % 12 IN (1, 5)
    UNION ALL
    SELECT k from (select 3 * a.j + b.j AS k FROM #Numbers a, #Numbers b) c WHERE k <= @MaxNumber AND k % 12 = 7
    UNION ALL
    SELECT k from (select 3 * a.j - b.j AS k FROM #Numbers a INNER JOIN #Numbers b ON a.i > b.i) c WHERE k <= @MaxNumber AND k % 12 = 11
) d GROUP BY k HAVING COUNT(*) IN (1, 3)
PRINT 'Checkpoint B: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'

--Calculation - Eliminate composites by sieving
DECLARE @i BIGINT
SET @i = 5
WHILE @i * @i < @MaxNumber
BEGIN
    DELETE #Primes WHERE i > @i and i % @i = 0
    SELECT @i = min(i) FROM #Primes WHERE i > @i
--    PRINT @i
END

--Show results
PRINT 'Finish: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'
SELECT COUNT(*) AS 'Number of primes', MAX(i) AS 'Max prime' FROM #Primes
--SELECT * FROM #Primes ORDER BY i

--Tidy up
DROP TABLE #Primes
DROP TABLE #Numbers

Ryan, I modified your script to use INT temp tables, instead of BIGINT, and got almost an 18% reduction in runtime.  The following is the result of finding all primes below 100 million.

Using BIGINT for the data types doesn't seem to be needed unless you are going over 2 billion in your prime number search.

Test with INT temp tables
Checkpoint A: 250 ms
Checkpoint B: 230573 ms
Finish: 652583 ms
Number of primes Max prime   Average of primes    
---------------- ----------- -------------------- 
5761455          99999989    48461680

Test with BIGINT temp tables
Checkpoint A: 250 ms
Checkpoint B: 280590 ms
Finish: 791850 ms
Number of primes Max prime            Average of primes    
---------------- -------------------- -------------------- 
5761455          99999989             48461680