Tek-Tips is the largest IT community on the Internet today!

Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!

Register Log in
  • Congratulations Mike Lewis on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!

SQL Server Puzzle:Prime Numbers 9

Status
Not open for further replies.
SQLDenis

SQLDenis

Programmer
Oct 1, 2005
5,575
0
0
US
Why wait until Friday
Okay here we go
This is what needs to be accomplished
Write SQL code that will put all Prime numbers between 1 and 1000000 ( 1 million) into a table and then select a count from that table

Rules
1 You have to write everything from scratch, meaning we should be able to execute the script on any computer and get the same result
2 Don't show any code until the 20th (Next Friday)
3 We should only show the time and recordcount so that people will have a general idea if their code is fast enough
example PIV 3.0 Ghz 2GB RAM runtime 21 seconds recordcount 567
People should post this every time they improve their code so that we can see what's going on
4 The first five people who sign up will run all the scripts and list the in execution time order or we can designate 5 people it doesn't matter
5 remember the fastest time wins, it doesn't have to look pretty


template below

Code: 
declare @d datetime,@d2 datetime
select @d = getdate()
declare @intPrimeNumberCount int
select @intPrimeNumberCount =0

/*
All other code goes here
*/

select @d2 = getdate()
select (@d2 -@d)as TimeElapsed,@intPrimeNumberCount as PrimeNumberCount

So this is a real SQL puzzle and no admin stuff here
Let me know what you think and good luck


Denis The SQL Menace
SQL blog:
Personal Blog:
 
Sort by date Sort by votes
vongrunt

1 is not a prime number.


The University Of Utah said:
A prime number is a natural number greater than 1 that can be divided evenly only by 1 and itself. Thus the first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Click to expand...

I would like to state that 'certain' hardcoded numbers should be allowed. To get my toaster to 'spit it out' within 15 seconds, I hardcoded a couple values. Nothing like Select 2 union all select 3 etc... though.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
2 is the smallest prime number...thats what i learned in my math class

-DNG
 
Upvote 0 Downvote
denis

Just for fun, I wondered how long it would take with the 'pure hard coded' method. So I did this...

Code: 
Create Table #T(Number Integer)

Insert Into #T
Select 2
Union All Select 3
Union All Select 5
Union All Select 7
Union All Select 11
[green]--etc.... all the way to 78,498 records[/green]

I got this error.
[red]Server: Msg 8621, Level 17, State 1, Line 3[/red]
Internal Query Processor Error: The query processor ran out of stack space during query optimization.


-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
And you didn't ran out of fingers and toes this time? :)

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)
[banghead]
 
Upvote 0 Downvote
This method....

Code: 
Create Table #T(Number Integer)

Insert Into #T Select 2
Insert Into #T Select 3
Insert Into #T Select 5
Insert Into #T Select 7
Insert Into #T Select 11
Insert Into #T Select 13
[green]--etc.... all the way to 78,498 records[/green]

... works, but it takes 1:38 on my computer. That's 6.5 times slower that calculating the numbers.

I suspect there's a way to hard code the numbers that would be faster, but that won't win me any stars. [wink]

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
Hehe... let's just say below 15 seconds things become interesting. [pipe]

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)
[banghead]
 
Upvote 0 Downvote
Interesting... unless you choose a different language. Now, I know this isn't fair (and won't win me any stars), but I implemented my logic for generating prime numbers in VB. The results are astonishing.

Here's a link to the VB app that I created. You will need the VB6 runtimes and the Microsoft Rich Text Box control to run this.

My VB Prime Number Generator

Just to let you know. It takes about 0.1 seconds to generate the prime numbers and then another .3 seconds to display them.

If anyone is interested, I will post the source code after the contest is over.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
Wonderful George,

Would definitely love to see the code...

Thanks

-DNG
 
Upvote 0 Downvote
DNG After the contest, I promise.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
'til Friday... how about shortest code possible?

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)
[banghead]
 
Upvote 0 Downvote
How would you define the shortest code?

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
Fewest bytes of code?

And we should test it on much less numbers (say, there are 168 primes in first 1000 numbers) for obvious reasons.

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)
[banghead]
 
Upvote 0 Downvote
How would the 'correct' answer for number 17 be determined assuming English as the language?

Up to 100 English and US English would be the same, but in English we use the word 'and' with the larger numbers which I believe is not used in US English.

[vampire][bat]
 
Upvote 0 Downvote
> Here is some good material for more SQL puzzles

To be honest, I am not sure...

Most of problems from there are procedural by nature. Find first N Fibonacci|perfect|Lychrel|Carmichael|blah numbers and things like that. Doing brute-force sucks. And translating complex algorithms to procedural SQL is like translating English to Klingon. Sure, there are some set-based tricks possible... but not much IMHO.

Now... using math knowledge to solve "real-life" problems is different story.

------
"There's a man... He's bald and wears a short-sleeved shirt, and somehow he's very important to me. I think his name is Homer."
(Jack O'Neill, Stargate)
[banghead]
 
Upvote 0 Downvote
Here's my VB Source code.

To replicate this, you will need a form with a command button, several labels, and a rich text box control.

Code: 
Option Explicit

Private Sub Command1_Click()
    
    Dim i As Long
    Dim j As Long
    Dim iCount As Long
    Dim arNumbers() As Boolean
    Dim sStart As Single
    Dim Primes() As String
    
    sStart = Timer
    
    ReDim arNumbers(2 To 1000000)
    
    For i = 2 To 1000000
        arNumbers(i) = True
    Next
    
    i = 2
    While i < 1000
        For j = (i + i) To UBound(arNumbers) Step i
            arNumbers(j) = False
        Next
        
        For j = i + 1 To UBound(arNumbers)
            If arNumbers(j) Then
                i = j
                Exit For
            End If
        Next
    Wend
    
    iCount = 0
    ReDim Primes(UBound(arNumbers))
    
    For i = LBound(arNumbers) To UBound(arNumbers)
        If arNumbers(i) Then
            Primes(iCount) = i
            iCount = iCount + 1
        End If
    Next
    
    ReDim Preserve Primes(iCount - 1)
    
    txtResults.Text = Join(Primes, vbCrLf)
    
    lblExecutionTime.Caption = Format(Timer - sStart, "0.00") & " Sec."
    lblCount.Caption = CStr(UBound(Primes) + 1)
    
End Sub

I did not 'try hard' to optimize this for speed. I was just amazed at the difference between SQL Server and VB.

-George

Strong and bitter words indicate a weak cause. - Fortune cookie wisdom
 
Upvote 0 Downvote
Status
Not open for further replies.

Similar threads

V
  • Question
xp_cmdshell vs psexec - this SQL server forgets credential to an W10 share
Replies
0
Views
312
Volvere
V
gbaughma
  • Locked
  • Question
SQL Performance
Replies
11
Views
275
pjw001
pjw001
elly00
  • Locked
  • Question
create sql view using batch file
Replies
5
Views
197
Mike Lewis
Mike Lewis
grnzbra
  • Locked
  • Question
T-SQL Dialog Box
Replies
8
Views
178
Chris Miller
Chris Miller
Andrzejek
  • Locked
  • Question
Eliminate pesky [ ] in SQL Management Studio
Replies
5
Views
215
SaltyTheFrog
SaltyTheFrog

Part and Inventory Search

Sponsor

Back
Top