Getting a Uniform Multiplicand and Multiplier from a Product

Help and Feedback Code Review
#1

I could not find anything about this online. I’ll explain what it means here, it basically means that I want to find two numbers that multiply together to make an answer. Multiplicand is the first number, Multiplier is the second and Product is the answer.

Uniform means closest, for example 1 * 100 = 100 but if I wanted it to be Uniform I would do 10 * 10 = 100. Square rooting will only give integers for square numbers. In the example below I use 234 which is not a square number.

local function Sort(A, B)
	return math.abs(A.Multiplier - A.Multiplicand) < math.abs(B.Multiplier - B.Multiplicand)
end

local function GetUniformMultiplicandAndMultiplier(Product)
	local Array = {}
	
	for Count = 1, Product do
		if Product % Count == 0 then
			table.insert(Array, {
				Multiplicand = Count,
				Multiplier = Product / Count
			})
		end
	end
	
	table.sort(Array, Sort)
	
	return Array[1], Array[1]
end

local Product = 234
local Dictionary = GetUniformMultiplicandAndMultiplier(Product)

print(("%d * %d = %d"):format(Dictionary.Multiplicand, Dictionary.Multiplier, Product)) --> 13 * 18 = 234

Efficiency, is this the best way to approach something like this, since I could not find anything online this is the method I have used. Maybe there is a better one.

1 Like
#2

If I understand correctly, an algorithm like this might be what you mean?

local function getMultiplier(target)
	local a = math.floor(math.sqrt(target))
	for i=1, a do
		if target % a == 0 then
			return a
		end
		a -= 1
	end
end

print(getMultiplier(234))

It looks for a factor closest to the square root, counting down (note counting down is more efficient than up). Once found, retrieving the second factor is easy. The function will return a value for any positive integer input number, since it will return 1 if the product is prime.

It’s still slow for big numbers. Probably more optimizations are possible if you are clever about it, but this is a simple solution that springs to mind.