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
SSC Eights!
SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)

Group: General Forum Members
Points: 875 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: 1841 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
SSC Eights!
SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)

Group: General Forum Members
Points: 875 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 (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)Grasshopper (20 reputation)

Group: General Forum Members
Points: 20 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
SSC Eights!
SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)SSC Eights! (875 reputation)

Group: General Forum Members
Points: 875 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 (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)SSC-Enthusiastic (180 reputation)

Group: General Forum Members
Points: 180 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 (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)SSC-Enthusiastic (124 reputation)

Group: General Forum Members
Points: 124 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 (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)Forum Newbie (3 reputation)

Group: General Forum Members
Points: 3 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 Guru
SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)SSC Guru (56K reputation)

Group: General Forum Members
Points: 56078 Visits: 40410

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.
If you think its expensive to hire a professional to do the job, wait until you hire an amateur. -- Red Adair

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

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