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.”
Man vet aldrig när man behöver lite primtal ;)