A prime number challenge.

I stumbled upon a challenge on a blog i follow, to find prime numbers using T-SQL. With a little bit of Wikipedia research, I’ve built a T-SQL version of the “sieve of Eratosthenes“.

--- Table variable to hold all values to test. We could make this
--- a real temp table to further improve performance.
DECLARE @ints TABLE (
    i    int NOT NULL,
    PRIMARY KEY CLUSTERED (i)
);

--- Populate work table with a series of integers..
WITH cte (i)
AS (    -- .. starting at 2
    SELECT 2 AS i UNION ALL
    SELECT i+1 FROM cte WHERE i<1000000)

INSERT INTO @ints (i)
SELECT i FROM cte
--- ... and we're already excluding some "obvious" primes,
--- by removing values that are divisible with 2, 3, 5, 7
--- and 11. This keeps the table size down and improves
--- performance.
WHERE (i=2 OR i%2!=0) AND
    (i=3 OR i%3!=0) AND
    (i=5 OR i%5!=0) AND
    (i=7 OR i%7!=0) AND
    (i=11 OR i%11!=0)
OPTION (MAXRECURSION 0)

DECLARE @p int, @i_count int
SELECT @p=1, @i_count=MAX(i) FROM @ints

--- Here's the loop. Starting at @p=2, we remove all
--- integers from the work table where the integer is
--- divisible with @p.
--- Then we set @p to the next available integer in
--- the table.
--- The loop goes on until we reach the square root of
--- the maximum number of integers.
WHILE (@p<SQRT(@i_count)) BEGIN
    SELECT @p=MIN(i) FROM @ints WHERE i>@p

    DELETE FROM @ints WHERE i>@p AND i%@p=0
END;

--- That's it.
SELECT i FROM @ints ORDER BY i

One thought on “A prime number challenge.

Let me hear your thoughts!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s