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