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

 Finding Primes Rate Topic Display Mode Topic Options
Author
 Message
 Posted Wednesday, December 27, 2006 11:43 AM
 Right there with Babe Group: General Forum Members Last Login: Tuesday, November 8, 2016 10:08 AM Points: 787, Visits: 341
 Comments posted here are about the content posted at http://www.sqlservercentral.com/columnists/kKellenberger/2782.asp Aunt KathiLinchpin People TeammateSQL Server MVPAuthor of Expert T-SQL Window Functions
Post #333029
 Posted Monday, January 29, 2007 3:07 AM
 SSCommitted Group: General Forum Members Last Login: Tuesday, May 29, 2012 11:22 AM Points: 1,755, Visits: 4,652
 Finding primes is something I worked on about 6 months ago (for fun, of course ). Here's a link to the work...http://www.sqlteam.com/forums/topic.asp?TOPIC_ID=69646It uses a sieve of Atkin approach, and in my tests back then, the function could find all primes below 100,000 in 0.5 seconds. Ryan RandallSolutions are easy. Understanding the problem, now, that's the hard part.
Post #340411
 Posted Monday, January 29, 2007 3:26 AM
 Right there with Babe Group: General Forum Members Last Login: Tuesday, November 8, 2016 10:08 AM Points: 787, Visits: 341
 Cool.  Looks like there are a lot of ways to solve this puzzle.  Aunt KathiLinchpin People TeammateSQL Server MVPAuthor of Expert T-SQL Window Functions
Post #340414
 Posted Monday, January 29, 2007 8:49 AM
 Grasshopper Group: General Forum Members Last Login: Wednesday, August 12, 2009 10:14 AM Points: 18, Visits: 167
 By checking the square root outside of the select statement, you will save the processor a number of extra calculations.  I modified it to be this: SELECT @NextIntSqrt = SQRT(@NextInt) IF NOT EXISTS (SELECT Prime FROM Primes WHERE @NextIntSqrt >= Prime AND @NextInt % Prime = 0) Cuts down the calculation time significantly.  I also adjusted the order of the filters in the WHERE clause.
Post #340512
 Posted Monday, January 29, 2007 8:59 AM
 Right there with Babe Group: General Forum Members Last Login: Tuesday, November 8, 2016 10:08 AM Points: 787, Visits: 341
 Good idea. Aunt KathiLinchpin People TeammateSQL Server MVPAuthor of Expert T-SQL Window Functions
Post #340515
 Posted Monday, January 29, 2007 10:58 AM
 SSC-Enthusiastic Group: General Forum Members Last Login: Monday, January 11, 2016 3:37 AM Points: 164, Visits: 375
 Rob FarleyLobsterPot Solutions & Adelaide SQL Server User GroupCompany: http://www.lobsterpot.com.auBlog: http://sqlblog.com/blogs/rob_farley
Post #340555
 Posted Monday, January 29, 2007 12:37 PM
 SSC-Enthusiastic Group: General Forum Members Last Login: Friday, March 19, 2010 1:30 PM Points: 110, Visits: 37
 Fun stuff.I tried to do something similar in VB several years ago...the trick was that I was trying to solve for primes bigger than any of the data types. I ran out of time before I solved it...but it sure was a fun exercise!
Post #340601
 Posted Monday, January 29, 2007 5:32 PM
 Forum Newbie Group: General Forum Members Last Login: Sunday, December 14, 2014 11:20 PM Points: 1, Visits: 136
 KathiIn the book you mentioned, Chris has Aspbergers Syndrome (rather than being autistic). There are many similarities, but people with Aspbergers for the most part can lead relatively 'normal' lives. There are varying degrees of both of course, and it's sometimes hard to make a clear distinction where one ends and the other begins. Regards,MItch
Post #340706
 Posted Monday, January 29, 2007 8:31 PM
 SSC-Forever Group: General Forum Members Last Login: Today @ 4:15 PM Points: 42,082, Visits: 39,476
 Hi Ryan,What did you come up with for the largest prime number found and how many prime numbers?   I wanna make sure I'm doing it right... --Jeff Moden"RBAR is pronounced "ree-bar" and is a "Modenism" for "Row-By-Agonizing-Row".First step towards the paradigm shift of writing Set Based code: Stop thinking about what you want to do to a row... think, instead, of what you want to do to a column." Helpful Links:How to post code problemsHow to post performance problems
Post #340729
 Posted Tuesday, January 30, 2007 2:59 AM
 SSC-Addicted Group: General Forum Members Last Login: Friday, June 17, 2011 6:28 AM Points: 422, Visits: 33
 My suggestion, on our SQL Server 2000 installation it finds all primes less than 5000000 in 54 seconds. But of course it depends on the hardware...   set nocount ongoselect top 5000000 identity(int, 1, 1) as Number into #Numbersfrom syscomments c1 cross join syscomments c2goalter table #Numbers add constraint PK_Numbers primary key clustered (Number)gocreate table #Primes(prime int primary key)godeclare @time datetimeselect @time = getdate()declare @i intset @i = 1while @i*@i < 5000000begin insert into #Primes select n.Number from #Numbers n where n.Number < (@i+1)*(@i+1) 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 #Primesselect datediff(ms, @time, getdate())drop table #Primesgodrop table #Numbersgo
Post #340767

 Permissions