最大公约数

代码片段

最大公约数

适用于 PostgreSQL

8.4

编写语言

SQL

依赖

无

使用 CTE，最大公约数 (gcd) 的计算非常简单。

CREATE OR REPLACE FUNCTION gcd( a bigint,  b bigint)
RETURNS bigint
IMMUTABLE
STRICT
LANGUAGE SQL
AS $$
WITH RECURSIVE t(a,b) AS (
    VALUES (abs($1)::bigint, abs($2)::bigint)
UNION ALL
    SELECT b, mod(a,b) FROM t
    WHERE b > 0
)
SELECT a FROM t WHERE b = 0
$$;

感谢 David Fetter 提供此查询。 感谢 Pasha Golub 提供了更快、更准确的版本。

从 PostgreSQL 13 开始，可以使用内置函数 gcd()（PostgreSQL 文档：数学函数 ）。