Is it possible to calculate the Greatest common divisor of a number?

Help and Feedback Scripting Support
#1

Odd question, yes, but it pops out of my mind if it is actually possible to calculate the GCD of a number using Lua’s math. Kind of challenging I guess?

#2

hey, i’m working in this challenge. I managed to do this in python without using gcd(), but i have some difficulties to “translate” my code into lua…

1 Like
#3

It’s probably not the BEST script ever, you can maybe “compact” it, but this should work:

function gcd(num1, num2)
local divisors1 = {}
local divisors2 = {}
local common_divisors = {}
for x = 1, num1, 1 do
	if num1 % x == 0 then
		table.insert(divisors1, 1, x)
	end
end


for x = 1, num2, 1 do
	if num2 % x == 0 then
		table.insert(divisors2, 1, x)
	end
end

for _, v in pairs(divisors1) do
	for _, v2 in pairs(divisors2) do
		if v == v2 then
			table.insert(common_divisors, 1, v)
		end
	end
end	

table.sort(common_divisors, function(a, b)
	return a > b
end)
print(common_divisors[1])
end

gcd(number1, number2)

number1 et number2 désignent les 2 nombres

1 Like
#4

This can be done using the euclidean algorithm for finding the greatest common divisor.

function gcd(a,b)
	if b ~= 0 then
		return gcd(b, a % b)
	else
		return math.abs(a)
	end
end
8 Likes