Technical Article

Table Valued Function to return a range of prime numbers

,

I just wrote this function just for the fun of it. 

It uses the sieve of Eratosthenes algorithm to find ranges of prime numbers and is a really fast method to generate lists of primes.

It also uses a dynamic inline tally table which is a modification of this http://www.sqlservercentral.com/articles/T-SQL/67899/ by Lynn Pettis

To get a list of primes between 1,000 and 10,000 just run the SQL statement: 

SELECT * FROM dbo.DynamicPrimes(10000, 1000) 

To find the count of primes between 2 and 100,000 just run:

SELECT COUNT(*) CountPrimes FROM dbo.DynamicPrimes(100000, 2) 

etcetera...

USE Test
GO
IF OBJECT_ID('[dbo].[DynamicPrimes]','TF') IS NULL
    EXEC('CREATE FUNCTION [dbo].[DynamicPrimes]() RETURNS @t TABLE(n int) BEGIN RETURN END')
GO
-- *****************************************************************
-- Author:      Jonathan Roberts
-- Create date: 31/03/2017
-- Description: Table Valued Function to return all prime numbers within a range.
--
-- Sample Call:
-- To find the all the primes between 1 and 100,000:
--     SELECT * FROM dbo.DynamicPrimes(100000, 1) 
-- To find the all the primes between 900,000 and 1,000,000:
--     SELECT * FROM dbo.DynamicPrimes(1000000, 00000) 
-- To count the how many primes between 2 and 1,000,000
--      SELECT COUNT(*) CountPrimes FROM dbo.DynamicPrimes(1000000, 2) 
-- *****************************************************************
ALTER FUNCTION dbo.DynamicPrimes
(
    @Max int = 100000,
    @Min int = 2
)
RETURNS @Primes TABLE (N int PRIMARY KEY CLUSTERED)
AS
BEGIN
    IF @Min < 2 SET @Min = 2;

      WITH L0(N) AS (SELECT 'Anything' FROM (VALUES(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) AS T(N)), -- 15 values
           L1(N) AS (SELECT A.N FROM L0 A, L0 B, L0 C, L0 D, L0 E, L0 F, L0 G), -- 15^8  values (2562890625 more than enough for max value of int)
           L2(N) AS (SELECT TOP (@Max) A.N FROM L1 A), 
           L3(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY N) FROM L2)
    INSERT INTO @Primes(N)
    SELECT N
      FROM (VALUES (2),(3),(5),(7),(11),(13),(17),(19),(23),(29),(31)) AS P(N)
     UNION ALL
    SELECT N
      FROM L3
     WHERE 0 NOT IN (N%2, N%3, N%5, N%7, N%11, N%13, N%17, N%19, N%23, N%29, N%31)
     ORDER BY N

    DECLARE @Prime as int
    SET @Prime = 37 -- Initialise to first prime above already selected primes
    WHILE @Prime <= SQRT(@Max) BEGIN

            DELETE @Primes
            WHERE N >= @Prime * @Prime
              AND N % @Prime = 0

            SELECT TOP(1) @Prime=N
              FROM @Primes P
             WHERE N > @Prime
             ORDER BY N

    END
    DELETE @Primes
     WHERE N < @Min

    RETURN

END
GO

Rate

4.67 (3)

You rated this post out of 5. Change rating

Share

Share

Rate

4.67 (3)

You rated this post out of 5. Change rating