April 8, 2009 at 1:42 pm
I have come up with this code(given below) in an effrot to create an stored procedure that will print the prime numbers between 1 and 500.
The problem is that the execution never stops when this code is executed. I am not sure if this approach is right or the code is wrong as a whole. When I change the position of (@i=@i+1) and place it after the 'END' word where it(@i=@i+1) is now, I get the only number 2 printed under messages tab and the execution still countinues.
I have worked on this for an ample amount of time now and thought of seeking valuable advice rather than scratching my head furtheron.
Your responses will be appreciated.
sincerely thankfully.
/******** PART OF THE STORED PROCEDURE ********/
DECLARE @i INT, @a INT, @count INT
SET @i = 1
WHILE (@i <= 500)
BEGIN
SET @count = 0
SET @a = 1
WHILE (@a <= @i)
BEGIN
IF (@i%@a=0)
BEGIN
SET @count = @count + 1
END
IF (@count = 2)
BEGIN
PRINT @i
SET @i = @i+1
END
END
END
________________________________________________________________
"The greatest ignorance is being proud of your learning"
April 8, 2009 at 1:58 pm
While I'm assuming this is a homework problem, and I normally don't help with those, this was interesting enough that I couldn't stop myself. 🙂
You have a number of flow-of-logic errors. For example, if you look at where you have your increment on @a, you'll notice that you'll never reach that if @i is not evenly divisible by @a. So, the moment you try to divide 3 by 2, it never increments @a to 3, but just loops. Even if you fix that, check what'll happen to your increment for @i when it hits 4. Since 4 is the first non-prime number, it has a problem with where the increment is in relation to the check for @count.
Try this version:
DECLARE
@i INT,
@a INT,
@count INT
SET @i = 1
WHILE (@i <= 500)
BEGIN
SET @count = 0
SET @a = 1
WHILE (@a <= @i)
BEGIN
IF (@i % @a = 0)
SET @count = @count + 1
END
IF (@count = 2)
PRINT @i
SET @i = @i + 1
END
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
April 8, 2009 at 2:31 pm
[p]ha ha !! That laugh was for your(@GSquared) assumption being true. Yes, it is a home work. But I did tried my best before seeking help and was looped in between 'BEGIN' and 'END' since I am new to the SQL platform.[/p]
Well, your solution worked perfectly !! I shall thank you for that, for your time spent on that.
And the quote is educative and nice too..
________________________________________________________________
"The greatest ignorance is being proud of your learning"
April 8, 2009 at 2:36 pm
A useful trick to Begin...End blocks, is indent everything inside them by one tab. Helps you see the flow and make sure that you actually get where you need to.
Glad I was able to both amuse and help you.
For future reference, if you have something that's homework, it's considered ethical to state that right up front in the question. Doing so, and showing what you've done already to try, just keeps it honest, and everyone likes that.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
April 8, 2009 at 10:33 pm
Didn't we do set-based prime sieves last year sometime? ...
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
April 12, 2009 at 4:58 am
And, to make it a bit faster, let's skip all of the even numbers after 2 (I suspect I've chosen a less than desirable way to do that)
DECLARE
@i INT,
@a INT,
@count INT
SET @i = 1
WHILE (@i <= 500)
BEGIN
SET @count = 0
SET @a = 1
WHILE (@a <= @i)
BEGIN
IF (@i % @a = 0)
SET @count = @count + 1
END
IF (@count = 2)
PRINT @i
SET @i = @i + case when @i < 3 then 1 else 2 end
END
April 12, 2009 at 2:14 pm
That's another useful condition we can use here to increase performance. As the query without the case condition takes a while to get executed.Your post is appreciated !!
Thanks @Ross.M
________________________________________________________________
"The greatest ignorance is being proud of your learning"
April 14, 2009 at 2:20 pm
I have been thinking about this topic in the back of my brain since I read the post this morning.
The initial attempt was good for a first attempt but the brute force method would not be best. By definition, the only values that we need to worry about are prime numbers for the check, since all other values would be divisible by these.
Using a Temp Table to store the primes, we could optimize as such:
(To get meaningful results, I increased the search to 10,000. The original algorithm took 170 seconds on an old test box. This optimized routine took 2 seconds. 100,000 numbers took 112 seconds)
DECLARE
@max-2 INT, -- Max number for prime search
@i INT, -- Counter for possible candidates
@count INT , -- row count of matches
@TimeStart DateTime , -- Time execution start
SET NOCOUNT ON
-- Create Temp Table for storing results
Create Table #Primes(PrimeNumber Int Not Null)
-- Initialize variables
SET @TimeStart = GetDate()
SET @max-2 = 10000
SET @count = 0
SET @i = 2
WHILE (@i <= @max-2)
BEGIN
SET @count = (SELECT COUNT(*) FROM #Primes WHERE (@i % PrimeNumber) = 0 )
If @count = 0
INSERT INTO #Primes(PrimeNumber) Values(@i)
SET @i = @i + 1
END
-- Output the results
SELECT * FROM #primes
-- output execution in seconds
print DateDiff(ss, GetDate(), @TimeEnd)
DROP TABLE #Primes
April 14, 2009 at 3:04 pm
Of course, the real way to get this kind of thing from SQL is to use sets. Like this:
set nocount on;
create table #Numbers (
Number smallint identity primary key);
go
insert into #Numbers
default values;
go 500
select N1.Number
from #Numbers N1
inner join #Numbers N2
on N1.Number%N2.Number = 0
group by N1.Number
having count(*) <= 2
order by N1.Number;
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
April 14, 2009 at 3:14 pm
I'm glad someone finally said that, Gus. All of my prime sieve stuff is in heavily nested CTE's and I did not want to to have to retrovert it to SQL 2000. 🙂
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
April 14, 2009 at 4:26 pm
GSquared (4/14/2009)
Of course, the real way to get this kind of thing from SQL is to use sets. Like this:
set nocount on;create table #Numbers (
Number smallint identity primary key);
go
insert into #Numbers
default values;
go 500
select N1.Number
from #Numbers N1
inner join #Numbers N2
on N1.Number%N2.Number = 0
group by N1.Number
having count(*) <= 2
order by N1.Number;
The above method takes 16 seconds to return the primes < 10000 on my PC.
The method I've come up with below takes 160 msec to do the same.
DECLARE @max-2 int
DECLARE @n int
SET NOCOUNT ON
SET @max-2 = 10000
CREATE TABLE #Primes (N int NOT NULL PRIMARY KEY)
INSERT INTO #Primes (N)
SELECT 2
UNION ALL
SELECT T.N
FROM Tally T
WHERE (T.N BETWEEN 3 AND @max-2)
AND ((T.N % 2) <> 0)
SET @n = 2
WHILE (1 = 1) BEGIN
SELECT TOP (1) @n = N
FROM #Primes
WHERE (N > @n)
ORDER BY N
IF (@@ROWCOUNT = 0) BREAK
DELETE #Primes
WHERE (N > @n)
AND ((N % @n) = 0)
END
SELECT N FROM #Primes
DROP TABLE #Primes
EDIT:
...and for comparison, this modification of Ray Hastie's query runs in about 220 msec on the same PC.
DECLARE @max-2 int
DECLARE @n int
SET NOCOUNT ON
SET @max-2 = 10000
CREATE TABLE #Primes(N int NOT NULL PRIMARY KEY)
INSERT INTO #Primes(N) VALUES(2)
SET @n = 3
WHILE (@n <= @max-2) BEGIN
IF NOT EXISTS (SELECT 1 FROM #Primes WHERE ((@n % N) = 0))
INSERT INTO #Primes(N) VALUES(@n)
SET @n = @n + 2
END
SELECT N FROM #Primes
DROP TABLE #Primes
EDIT 2:
In this optimized version of GSquared's query, the query completes in about 6 seconds.
SELECT N1.N
FROM Tally N1
INNER JOIN Tally N2
ON (N2.N > 0 AND N2.N < N1.N AND (N1.N % N2.N) = 0)
WHERE (N1.N BETWEEN 2 AND 10000)
AND (N1.N = 2 OR (N1.N % 2) <> 0)
GROUP BY N1.N
HAVING (COUNT(*) = 1)
ORDER BY N1.N
April 14, 2009 at 7:56 pm
Here's an improved version of GSquared's set-based method.
create table #PR100 (Prime smallint primary key);
insert into #PR100
select T.N
from Tally T
left join (Select 2 as Prime
UNION ALL Select 3
UNION ALL Select 5
UNION ALL Select 7
) P1 on T.N%P1.Prime = 0 and T.N!=P1.Prime
where T.N between 2 and 100
group by T.N
having count(P1.Prime) = 0
select T.N
from Tally T
left join #PR100 P1 on T.N%P1.Prime = 0 and T.N!=P1.Prime
where T.N between 2 and 10000
group by T.N
having count(P1.Prime) = 0
order by T.N;
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
April 15, 2009 at 3:00 am
Barry,
Yep, your improved set-based query is 55% faster than my WHILE loop for primes < 10000 on my machine.
--Andrew
April 15, 2009 at 3:18 am
Changing the != operator to > in the LEFT JOINs gives another 10-15% performance improvement.
CREATE TABLE #PR100 (Prime smallint primary key);
INSERT INTO #PR100
SELECT T.N
FROM Tally T
LEFT JOIN (
SELECT 2 AS Prime
UNION ALL SELECT 3
UNION ALL SELECT 5
UNION ALL SELECT 7
) P1 ON ((T.N % P1.Prime) = 0) AND (T.N > P1.Prime)
WHERE (T.N BETWEEN 2 AND 100)
GROUP BY T.N
HAVING (COUNT(P1.Prime) = 0)
SELECT T.N
FROM Tally T
LEFT JOIN #PR100 P1 ON ((T.N % P1.Prime) = 0) AND (T.N > P1.Prime)
WHERE (T.N BETWEEN 2 AND 10000)
GROUP BY T.N
HAVING (COUNT(P1.Prime) = 0)
ORDER BY T.N;
April 15, 2009 at 7:02 am
andrewd.smith (4/15/2009)
Barry,Yep, your improved set-based query is 55% faster than my WHILE loop for primes < 10000 on my machine.
--Andrew
Really? Huh, I learn something new every day!
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font]
Viewing 15 posts - 1 through 15 (of 16 total)
You must be logged in to reply to this topic. Login to reply