Using T-SQL to find the Greatest Common Divisor (GCD) for any number of integers

Problem

I was given the task to write a process to find the greatest common divisor (GCD) of two or more integers.  By definition, in mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.  So, in this tip I will show you the code I came up with to solve this task.

Solution

The procedure shown in this tip does the mathematical operation of finding the greatest common divisor of any number of integer type values.

For example, the GCD of 8 and 12 is 4.

The following procedure is a suggested T-SQL solution for this task and does the mathematical operation by using T-SQL equivalent methods.

The algorithm used in the procedure that calculates the GCD for each pair of integers is called Euclid's algorithm named after the Greek mathematician.

1. My solution involves creating a rather simple T-SQL stored procedure in SQL Server application database, called dbo.dbo.usp_MultiGCD that will take a comma delimited string, parse it and insert all its parsed values into a table variable.
2. The table variable is indexed by an identity column.
3. The first loop of the procedure will be dedicated to parsing the string and filling the table variable.
4. The second while loop calculates the common GCD for the series of integers by calculating GCD from Euclid's algorithm for the first two integers from the table variable, then for the result and the third integer, then for the fourth integer value and so on until it reaches the end of the table variable.
5. The resulting GCD number is the output parameter for the procedure.

SQL Server Code to Calculate Greatest Common Divisor

Here is the code.  This creates a stored procedure, but you run the code as is or also create a function with a few minor tweaks.

```-- =================================================================================================
-- Author:         Eli Leiba
-- Create date:    12-2018
-- Procedure Name: dbo.usp_MultiGCD
-- Description:
--   The procedure gets a comma separated string in format I1, I2, I3, I4, ………In
--   Where Ii represents an integer number.
--   The procedure calculated as an output value the greatest common divisor (GCD) for all of
--   These integer values.
-- =================================================================================================
CREATE PROCEDURE dbo.usp_MultiGCD (@str VARCHAR (500), @gcd INT OUTPUT)
AS
BEGIN
DECLARE @tb TABLE (i INT identity, spdata NVARCHAR (max))
DECLARE @strt INT
DECLARE @end INT
DECLARE @a INT
DECLARE @b INT
DECLARE @t INT
DECLARE @cnt INT
DECLARE @ind INT

SET NOCOUNT ON
SELECT @strt = 1, @end = CHARINDEX (',', @str)
WHILE @strt < LEN (@str) + 1
BEGIN
IF @end = 0 SET @end = LEN (@str) + 1
INSERT INTO @tb (spdata) VALUES (SUBSTRING (@str, @strt, @end - @strt))
SET @strt = @end + 1
SET @end = CHARINDEX (',', @str, @strt)
END

SELECT @cnt = max (i) FROM @tb
SELECT @a = convert (INT, spdata) FROM @tb WHERE i = 1
SET @ind = 2
WHILE @ind <= @cnt
BEGIN
SELECT @b = convert (INT, spdata) FROM @tb WHERE i = @ind
WHILE (@b % @a) != 0
BEGIN
SET @t = @b % @a
SET @b = @a
SET @a = @t
END
SET @ind = @ind + 1
END
SET @gcd = @a
END
GO
```

Example Stored Procedure Usage

The following script finds the greatest common divisor (GCD) for the following series of integers (all numbers are positive, non-zero integer values):

• Series1: 80,20,40,12,16
• Series2: 100,25,55,90,10
```declare @g int
exec dbo.usp_MultiGCD '80,20,40,12,16' ,@g OUT
PRINT @g

exec dbo.usp_MultiGCD '100,25,55,90,10' ,@g OUT
PRINT @g
```

And the result is:

• For Series1: 4
• For Series2: 5
Next Steps
• You can create and compile this simple procedure in your application database and use it as a simple TSQL tool for calculating the greatest common divisor for any number of given integers.
• Modify the code to work as a function.
• Modify the code to take table input instead of using a string.
• The procedure should work for just about any version of SQL Server including (2005, 2008, 2012, 2014, 2016 and 2017).
• The procedure was tested on SQL Server 2014 Standard and SQL Server 2017 Developer editions

Last Updated: 2019-01-09 Eli Leiba is a senior application DBA, a teacher and a senior database consultant with 19 years of RDBMS experience.

View all my tips
Related Resources

 Wednesday, January 16, 2019 - 9:28:48 AM - Arun Sharma Back To Top Here is a Set-based approach. ```DECLARE @Str VARCHAR(50) = '80,20,40,12,16'; WITH Nums (N) AS ( SELECT TOP 1000 ROW_NUMBER() OVER (ORDER BY (SELECT 1)) FROM SYS.SYSCOLUMNS ), String (Num,Number) AS ( SELECT ROW_NUMBER() OVER (ORDER BY N), CONVERT(INT,SUBSTRING(',' + @Str + ',',N + 1,CHARINDEX(',',',' + @Str + ',',N + 1) - N - 1)) FROM Nums WHERE N < LEN(',' + @Str + ',') AND SUBSTRING(',' + @Str + ',',N,1) = ',' ), Divisors AS ( SELECT *,Modulo = Number % N,Rnk = ROW_NUMBER() OVER (PARTITION BY N ORDER BY Number) FROM String CROSS APPLY Nums WHERE N <= (SELECT MIN(Number) FROM String) AND Number % N = 0 ) SELECT GCD = MAX(N) FROM Divisors WHERE Modulo = 0 AND Rnk = (SELECT COUNT(*) FROM String); ```