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

By: Eli Leiba   |   Updated: 2019-01-09   |   Comments (1)   |   Related: > TSQL

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

About the author

Eli Leiba is a senior application DBA, a teacher and a senior database consultant with 19 years of RDBMS experience.

This author pledges the content of this article is based on professional experience and not AI generated.

View all my tips