Learn more about SQL Server tools

mssqltips logo
 

Tutorials          DBA          Dev          BI          Career          Categories          Webcasts          Whitepapers          Today's Tip          Join

Tutorials      DBA      Dev      BI      Categories      Webcasts

DBA    Dev    BI    Categories

 

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


By:   |   Last Updated: 2019-01-09   |   Comments (1)   |   Related Tips: More > T-SQL

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


next webcast button


next tip button



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

View all my tips




Post a comment or let the author know this tip helped.

All comments are reviewed, so stay on subject or we may delete your comment. Note: your email address is not published. Required fields are marked with an asterisk (*).

*Name    *Email    Email me updates 


Signup for our newsletter
 I agree by submitting my data to receive communications, account updates and/or special offers about SQL Server from MSSQLTips and/or its Sponsors. I have read the privacy statement and understand I may unsubscribe at any time.



    



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 &lt; 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 &lt;= (SELECT MIN(Number) FROM String)
AND Number % N = 0
)
SELECT GCD = MAX(N)
FROM Divisors
WHERE Modulo = 0
AND Rnk = (SELECT COUNT(*) FROM String);

Learn more about SQL Server tools