Creating Stored Procedure in SQL server 2000 for Printing Prime Numbers

  • 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

    SET @a = @a + 1

    END

    IF (@count = 2)

    BEGIN

    PRINT @i

    SET @i = @i+1

    END

    END

    END

    ________________________________________________________________
    "The greatest ignorance is being proud of your learning"

  • 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

    SET @a = @a + 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

  • [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"

  • 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

  • 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]

  • 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

    SET @a = @a + 1

    END

    IF (@count = 2)

    PRINT @i

    SET @i = @i + case when @i < 3 then 1 else 2 end

    END

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

  • 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

  • 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

  • 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]

  • 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

  • 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]

  • Barry,

    Yep, your improved set-based query is 55% faster than my WHILE loop for primes < 10000 on my machine.

    --Andrew

  • 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;

  • 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