## Finding Primes

 Author Message RyanRandall SSCertifiable Group: General Forum Members Points: 6105 Visits: 4652 Hi Jeff,Here's some code so you can run it yourself. I'll add some run results in the next post.--InputsDECLARE @MaxNumber INTSET @MaxNumber = 5000000--PreparationSET NOCOUNT ONDECLARE @Time DATETIMESELECT @Time = GETDATE()--Preparation - Numbers tableDECLARE @SqrtMaxNumber INTSET @SqrtMaxNumber = SQRT(@MaxNumber)SET ROWCOUNT @SqrtMaxNumberCREATE 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 c4SET ROWCOUNT 0UPDATE #Numbers SET j = i*iPRINT '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 #PrimesSELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 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 sievingDECLARE @i BIGINTSET @i = 5WHILE @i * @i < @MaxNumberBEGIN DELETE #Primes WHERE i > @i and i % @i = 0 SELECT @i = min(i) FROM #Primes WHERE i > @i PRINT @iEND--Show resultsPRINT '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 #PrimesSELECT * FROM #Primes ORDER BY i--Tidy upDROP TABLE #PrimesDROP TABLE #Numbers Ryan RandallSolutions are easy. Understanding the problem, now, that's the hard part. RyanRandall SSCertifiable Group: General Forum Members Points: 6105 Visits: 4652 Here's a selection of results when I run the above code on a server here. 39 seconds to find all primes below 5 million, and 18 minutes to find all primes below 100 million. DECLARE @Results TABLE (MaxNumber INT, CheckpointA INT, CheckpointB INT, Finish INT, NumberOfPrimes INT, MaxPrime INT, AverageOfPrimes INT, Seconds AS CAST(Finish AS DECIMAL) / 1000, Minutes AS CAST(Finish AS DECIMAL) / 60000, Time AS CAST(Finish / 60000 AS VARCHAR(5)) + ':' + RIGHT('0' + CAST(Finish / 1000 % 60 AS VARCHAR(2)), 2)) INSERT @Results SELECT 1000, 60, 93, 106, 168, 997, 453UNION ALL SELECT 5000, 76, 123, 140, 669, 4999, 2314UNION ALL SELECT 10000, 76, 156, 186, 1229, 9973, 4667UNION ALL SELECT 50000, 76, 280, 360, 5133, 49999, 23575UNION ALL SELECT 100000, 76, 466, 656, 9592, 99991, 47372UNION ALL SELECT 500000, 76, 1250, 2576, 41538, 499979, 238678UNION ALL SELECT 1000000, 93, 2203, 5516, 78498, 999983, 478361UNION ALL SELECT 5000000, 110, 10156, 39280, 348513, 4999999, 2406213UNION ALL SELECT 10000000, 93, 20030, 93403, 664579, 9999991, 4820081UNION ALL SELECT 50000000, 123, 208930, 843080, 3001134, 49999991, 24197369UNION ALL SELECT 100000000, 140, 466970, 1089933, 5761455, 99999989, 48461680 SELECT * FROM @Results /* ResultsMaxNumber CheckpointA CheckpointB Finish NumberOfPrimes MaxPrime AverageOfPrimes Seconds Minutes Time--------- ----------- ----------- ------- -------------- -------- --------------- ----------- ---------- -----1000 60 93 106 168 997 453 0.106000 0.001766 0:005000 76 123 140 669 4999 2314 0.140000 0.002333 0:0010000 76 156 186 1229 9973 4667 0.186000 0.003100 0:0050000 76 280 360 5133 49999 23575 0.360000 0.006000 0:00100000 76 466 656 9592 99991 47372 0.656000 0.010933 0:00500000 76 1250 2576 41538 499979 238678 2.576000 0.042933 0:021000000 93 2203 5516 78498 999983 478361 5.516000 0.091933 0:055000000 110 10156 39280 348513 4999999 2406213 39.280000 0.654666 0:3910000000 93 20030 93403 664579 9999991 4820081 93.403000 1.556716 1:3350000000 123 208930 843080 3001134 49999991 24197369 843.080000 14.051333 14:03100000000 140 466970 1089933 5761455 99999989 48461680 1089.933000 18.165550 18:09*/ Ryan RandallSolutions are easy. Understanding the problem, now, that's the hard part. Michael Valentine Jones SSC-Insane Group: General Forum Members Points: 23863 Visits: 11923 Good stuff Ryan!Did you compare the runtime against any of the other code posted on this thread? Jesper-244176 SSCrazy Group: General Forum Members Points: 2574 Visits: 33 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 willbe a bit slower.I have used the following in my test: /*************** MY CODE ******************/set nocount ongodeclare @time datetimeselect @time = getdate()DECLARE @MaxNumber INTSET @MaxNumber = 5000000SET ROWCOUNT @MaxNumberselect identity(int, 1, 1) as Number into #Numbersfrom syscomments c1 cross join syscomments c2 cross join syscomments c3SET ROWCOUNT 0alter table #Numbers add constraint PK_Numbers primary key clustered (Number)create table #Primes(prime int primary key)declare @i int, @limit intset @i = 1while @i*@i < @MaxNumberbegin 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 + 1end--select * from #PrimesPRINT 'Finish: ' + CAST(DATEDIFF(ms, @Time, GETDATE()) AS VARCHAR(10)) + ' ms'SELECT COUNT(*) AS 'Number of primes', MAX(prime) AS 'Max prime' FROM #Primesdrop table #Primesgodrop table #Numbersgo /******** RYAN'S CODE************************/ --InputsDECLARE @MaxNumber INTSET @MaxNumber = 5000000--PreparationSET NOCOUNT ONDECLARE @Time DATETIMESELECT @Time = GETDATE()--Preparation - Numbers tableDECLARE @SqrtMaxNumber INTSET @SqrtMaxNumber = SQRT(@MaxNumber)SET ROWCOUNT @SqrtMaxNumberCREATE 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 c2SET ROWCOUNT 0UPDATE #Numbers SET j = i*iPRINT '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 #PrimesSELECT 2 UNION ALL SELECT 3 UNION ALLSELECT 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 sievingDECLARE @i BIGINTSET @i = 5WHILE @i * @i < @MaxNumberBEGIN DELETE #Primes WHERE i > @i and i % @i = 0 SELECT @i = min(i) FROM #Primes WHERE i > @i-- PRINT @iEND--Show resultsPRINT '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 upDROP TABLE #PrimesDROP TABLE #Numbers Michael Valentine Jones SSC-Insane Group: General Forum Members Points: 23863 Visits: 11923 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 tablesCheckpoint A: 250 msCheckpoint B: 230573 msFinish: 652583 msNumber of primes Max prime Average of primes ---------------- ----------- -------------------- 5761455 99999989 48461680``Test with BIGINT temp tablesCheckpoint A: 250 msCheckpoint B: 280590 msFinish: 791850 msNumber of primes Max prime Average of primes ---------------- -------------------- -------------------- 5761455 99999989 48461680`` `` ` Mitch Wheat SSChasing Mays Group: General Forum Members Points: 645 Visits: 50 Can I suggest you re-read the book: "...of the story is a 15 year old autistic boy" He is not autistic. He has aspergers syndrome. Whilst there are some similarities, they are world's apart.