Recent PostsRecent Posts Popular TopicsPopular Topics
 Home Search Members Calendar Who's On

 Finding Primes Rate Topic Display Mode Topic Options
Author
 Message
 Posted Tuesday, January 30, 2007 6:40 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, May 29, 2012 11:22 AM Points: 1,755, Visits: 4,652
 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.
Post #340821
 Posted Tuesday, January 30, 2007 6:50 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, May 29, 2012 11:22 AM Points: 1,755, Visits: 4,652
 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.
Post #340825
 Posted Tuesday, January 30, 2007 10:31 PM
 Hall of Fame Group: General Forum Members Last Login: 2 days ago @ 1:39 PM Points: 3,021, Visits: 10,987
 Good stuff Ryan!Did you compare the runtime against any of the other code posted on this thread?
Post #341178
 Posted Wednesday, January 31, 2007 1:44 AM
 SSC-Addicted Group: General Forum Members Last Login: Friday, June 17, 2011 6:28 AM Points: 422, 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
Post #341208
 Posted Wednesday, January 31, 2007 4:37 PM
 Hall of Fame Group: General Forum Members Last Login: 2 days ago @ 1:39 PM Points: 3,021, Visits: 10,987
 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`` `` `
Post #341493
 Posted Monday, December 31, 2007 10:32 PM
 Mr or Mrs. 500 Group: General Forum Members Last Login: Wednesday, August 29, 2012 10:47 PM Points: 573, 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.
Post #437691

 Permissions