Module:Utils: Difference between revisions

← Older edit Newer edit →

@@ Line 67: / Line 67: @@
 	primes[n] = true
 	return true
+end
+-- returns prime factorization of integer n > 1; cannot be used with {{#invoke:}}
+-- note: the order of keys is not specified for Lua tables
+function p.prime_factorization_raw(n)
+	local factors = {}
+	local m = n
+	for i = 2, n do
+		while m % i == 0 do
+			factors[i] = factors[i] or 0
+			factors[i] = factors[i] + 1
+			m = m / i
+		end
+		if m == 1 then
+			break
+		end
+	end
+	return factors
 end