Click here to monitor SSC
SQLServerCentral is supported by Redgate
 
Log in  ::  Register  ::  Not logged in
 
 
 


Finding Primes


Finding Primes

Author
Message
Kathi Kellenberger
Kathi Kellenberger
Right there with Babe
Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)

Group: General Forum Members
Points: 787 Visits: 341
Comments posted here are about the content posted at http://www.sqlservercentral.com/columnists/kKellenberger/2782.asp

Aunt Kathi
Linchpin People Teammate
SQL Server MVP
Author of Expert T-SQL Window Functions
RyanRandall
RyanRandall
SSCommitted
SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)SSCommitted (1.8K reputation)

Group: General Forum Members
Points: 1761 Visits: 4652

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.
Kathi Kellenberger
Kathi Kellenberger
Right there with Babe
Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)

Group: General Forum Members
Points: 787 Visits: 341
Cool.  Looks like there are a lot of ways to solve this puzzle.

Aunt Kathi
Linchpin People Teammate
SQL Server MVP
Author of Expert T-SQL Window Functions
Jason1972
Jason1972
Grasshopper
Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)Grasshopper (18 reputation)

Group: General Forum Members
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.


Kathi Kellenberger
Kathi Kellenberger
Right there with Babe
Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)Right there with Babe (787 reputation)

Group: General Forum Members
Points: 787 Visits: 341
Good idea.

Aunt Kathi
Linchpin People Teammate
SQL Server MVP
Author of Expert T-SQL Window Functions
Rob Farley
Rob Farley
SSC-Enthusiastic
SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)SSC-Enthusiastic (166 reputation)

Group: General Forum Members
Points: 166 Visits: 375
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
GregLyon
GregLyon
SSC-Enthusiastic
SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)SSC-Enthusiastic (110 reputation)

Group: General Forum Members
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!



Mitch Wheat-379974
Mitch Wheat-379974
Forum Newbie
Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)Forum Newbie (1 reputation)

Group: General Forum Members
Points: 1 Visits: 136

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


Jeff Moden
Jeff Moden
SSC-Forever
SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)SSC-Forever (44K reputation)

Group: General Forum Members
Points: 44968 Visits: 39863

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.
Although they tell us that they want it real bad, our primary goal is to ensure that we dont actually give it to them that way.
Although change is inevitable, change for the better is usually not.
Just because you can do something in PowerShell, doesnt mean you should. Wink

Helpful Links:
How to post code problems
How to post performance problems
Forum FAQs
Jesper-244176
Jesper-244176
SSC-Addicted
SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)SSC-Addicted (422 reputation)

Group: General Forum Members
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

 


Go


Permissions

You can't post new topics.
You can't post topic replies.
You can't post new polls.
You can't post replies to polls.
You can't edit your own topics.
You can't delete your own topics.
You can't edit other topics.
You can't delete other topics.
You can't edit your own posts.
You can't edit other posts.
You can't delete your own posts.
You can't delete other posts.
You can't post events.
You can't edit your own events.
You can't edit other events.
You can't delete your own events.
You can't delete other events.
You can't send private messages.
You can't send emails.
You can read topics.
You can't vote in polls.
You can't upload attachments.
You can download attachments.
You can't post HTML code.
You can't edit HTML code.
You can't post IFCode.
You can't post JavaScript.
You can post emoticons.
You can't post or upload images.

Select a forum

































































































































































SQLServerCentral


Search