Click here to monitor SSC
SQLServerCentral is supported by Red Gate Software Ltd.
 
Log in  ::  Register  ::  Not logged in
 
 
 
        
Home       Members    Calendar    Who's On


Add to briefcase 12»»

Finding Primes Expand / Collapse
Author
Message
Posted Wednesday, December 27, 2006 11:43 AM


Right there with Babe

Right there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with Babe

Group: General Forum Members
Last Login: Tuesday, October 7, 2014 8:32 AM
Points: 769, Visits: 256
Comments posted here are about the content posted at http://www.sqlservercentral.com/columnists/kKellenberger/2782.asp

Aunt Kathi
Microsoft
(Former SQL Server MVP)
Post #333029
Posted Monday, January 29, 2007 3:07 AM


SSCommitted

SSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommittedSSCommitted

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=69646

It 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 Randall

Solutions 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

Right there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with Babe

Group: General Forum Members
Last Login: Tuesday, October 7, 2014 8:32 AM
Points: 769, Visits: 256
Cool.  Looks like there are a lot of ways to solve this puzzle. 

Aunt Kathi
Microsoft
(Former SQL Server MVP)
Post #340414
Posted Monday, January 29, 2007 8:49 AM
Grasshopper

GrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopperGrasshopper

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

Right there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with BabeRight there with Babe

Group: General Forum Members
Last Login: Tuesday, October 7, 2014 8:32 AM
Points: 769, Visits: 256
Good idea.

Aunt Kathi
Microsoft
(Former SQL Server MVP)
Post #340515
Posted Monday, January 29, 2007 10:58 AM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-Enthusiastic

Group: General Forum Members
Last Login: Saturday, August 2, 2014 1:58 AM
Points: 164, Visits: 368
More on primes at:

http://blogs.technet.com/wardpond/archive/2006/09/23/458344.aspx

http://blogs.technet.com/wardpond/archive/2006/09/23/458580.aspx

http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime_numbers.aspx

http://sqlblog.com/blogs/hugo_kornelis/archive/2006/09/23/Prime_numbers.aspx#comments

And of course, at my _old_ blog at:

http://robfarley.blogspot.com/2006/09/primes.html

http://robfarley.blogspot.com/2006/09/more-on-primes.html

All lots of fun...



Rob Farley
LobsterPot Solutions & Adelaide SQL Server User Group
Company: http://www.lobsterpot.com.au
Blog: http://sqlblog.com/blogs/rob_farley
Post #340555
Posted Monday, January 29, 2007 12:37 PM
SSC-Enthusiastic

SSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-EnthusiasticSSC-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

Forum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum NewbieForum Newbie

Group: General Forum Members
Last Login: Monday, October 27, 2014 9:45 PM
Points: 1, Visits: 132

Kathi

In 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-Dedicated

SSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-DedicatedSSC-Dedicated

Group: General Forum Members
Last Login: Today @ 12:23 PM
Points: 35,403, Visits: 31,965

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."

(play on words) "Just because you CAN do something in T-SQL, doesn't mean you SHOULDN'T." --22 Aug 2013

Helpful Links:
How to post code problems
How to post performance problems
Post #340729
Posted Tuesday, January 30, 2007 2:59 AM
SSC-Addicted

SSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-AddictedSSC-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 on
go

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

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

create table #Primes(prime int primary key)
go

declare @time datetime
select @time = getdate()

declare @i int
set @i = 1
while @i*@i < 5000000
begin
 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 + 1
end

--select * from #Primes

select datediff(ms, @time, getdate())

drop table #Primes
go

drop table #Numbers
go

 

Post #340767
« Prev Topic | Next Topic »

Add to briefcase 12»»

Permissions Expand / Collapse