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: More > TSQL
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.
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.
- 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.
- The table variable is indexed by an identity column.
- The first loop of the procedure will be dedicated to parsing the string and filling the table variable.
- 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.
- 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
- 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
View all my tips
Article Last Updated: 2019-01-09