TSQL Script to find the Largest Prime Number

Rajnilari2015
Posted by in Sql Server category on for Beginner level | Points: 250 | Views : 474 red flag

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


 Download source code for TSQL Script to find the Largest Prime Number

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.

Page copy protected against web site content infringement by Copyscape

About the Author

Rajnilari2015
Full Name: Niladri Biswas (RNA Team)
Member Level: Platinum
Member Status: Member,Microsoft_MVP,MVP
Member Since: 3/17/2015 2:41:06 AM
Country: India
-- Thanks & Regards, RNA Team


Login to vote for this post.

Comments or Responses

Login to post response

Comment using Facebook(Author doesn't get notification)