# 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.”

1. Erik

Coolt :)
Man vet aldrig när man behöver lite primtal ;)

This site uses Akismet to reduce spam. Learn how your comment data is processed.