In this article, we will look into how to find the largest Prime Number given a set of numbers using TSQL

## Introduction

From WhatIs.com

A prime number is a whole number greater than 1, whose only two whole-number factors are 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

In this article, we will look into how to find the largest Prime Number given a set of numbers using TSQL

## Straight to program

Let us first declare a table with some values as under

--Declare a table with some numbers
DECLARE @NumbersTbl TABLE (Number INT)
--Insert some records to it
INSERT INTO @NumbersTbl
VALUES (204723),(104723),(104021),(558),(-27),(104727),(104729),(665),(103981),(9277)
--Project the record
SELECT *
FROM @NumbersTbl
/*
Number
-------
204723
104723
104021
558
-27
104727
104729
665
103981
9277
*/

Now let us write the program step by step. In the first step, we will declare a variable that will hold the largest number from the @NumbersTbl as under

--Step 1: Declare a variable that will hold the largest number from the @NumbersTbl
DECLARE @biggestNumber INT
SELECT @biggestNumber = MAX(Number)
FROM @NumbersTbl
SELECT BiggestNumber= @biggestNumber
/*
BiggestNumber
-------------
204723
*/

As a next step, we will generate a number table from 2 till the biggest number. This we will achieve through a recursive CTE as shown under

-- Step 2: Generate a number table from 2 till the biggest number
;WITH NumCTE AS (
SELECT 2 AS Digits
UNION ALL
SELECT Digits+1
FROM NumCTE
WHERE Digits < @biggestNumber
)

Now we will apply a trick. Let us consider two numbers say 11 and 15. Now the biggest among them is 15. Let us start dividing the number 13 from 2 to 15 and the modulus result for that will be

Now let us do the same for the number 15 and the result is as under

From this we can infer that, __if the number is prime it should be divided equally only once (by that number itself)__ as per the definition mentioned above and henceforth, it should have only two factors i.e. 1 and itself. Hence, 13 is prime and not 15. Now we will apply this logic to our TSql Script in our next step

-- Step 3: Modulo count
SELECT Number,[Count(Result = Dividend % Divisor)]= COUNT(c.Digits)
FROM @NumbersTbl t
CROSS JOIN NumCTE c
WHERE t.Number % c.Digits=0
GROUP BY t.Number
OPTION (MAXRECURSION 0)

We are performing a Cartesian Product(CROSS JOIN) inorder to get the modulo of each number between @NumbersTbl and NumCTE. Primes are those whose modulo (Dividend % Divisor) are equal to 1.

We can now filter by primes by using the "Having Clause" as under

-- Step 3: Filter Modulo count for obtaining Primes
SELECT Number,[Count(Result = Dividend % Divisor)]= COUNT(c.Digits)
FROM @NumbersTbl t
CROSS JOIN NumCTE c
WHERE t.Number % c.Digits=0
GROUP BY t.Number
HAVING COUNT(c.Digits) = 1
OPTION (MAXRECURSION 0)

As a last step we need to get the largest Prime Numbers which can be obtained by using the MAX() function. The complete TSQL Script is as under

--Declare a table with some numbers
DECLARE @NumbersTbl TABLE (Number INT)
--Insert some records to it
INSERT INTO @NumbersTbl
VALUES (204723),(104723),(104021),(558),(-27),(104727),(104729),(665),(103981),(9277)
--Step 1: Declare a variable that will hold the largest number from the @NumbersTbl
DECLARE @biggestNumber INT
SELECT @biggestNumber = MAX(Number)
FROM @NumbersTbl
-- Step 2: Generate a number table from 2 till the biggest number
;WITH NumCTE AS (
SELECT 2 AS Digits
UNION ALL
SELECT Digits+1
FROM NumCTE
WHERE Digits < @biggestNumber
)
-- Step 3: Filter Modulo count for obtaining Primes
,GetAllPrimes AS(
SELECT Number
FROM @NumbersTbl t
CROSS JOIN NumCTE c
WHERE t.Number % c.Digits=0
GROUP BY t.Number
HAVING COUNT(c.Digits) = 1)
-- Step 4: Obtain the largest prime number
SELECT [Largest Prime Number] = MAX(Number)
FROM GetAllPrimes
OPTION (MAXRECURSION 0)
/*
Largest Prime Number
--------------------
104729
*/

## Conclusion

In this article we have learnt how to find the Largest Prime Number. In the process we learnt how to write recursive CTE, use Cartesian Product, logic to obtain prime numbers and many more. Hope this will be useful. Thanks for reading. Zipped file attached.