ユークリッドの互除法.sql

with recursive euclid(x,y) as (
    select 56,12
    union all
    select y, x%y from euclid
    where y != 0
)
select x from euclid
where y = 0;

/*
4 = gcd(56,12)
*/

with recursive euclid(x,y) as (
    select 4563132817,31176473253
    union all
    select y, x%y from euclid
    where y != 0
)
select x from euclid
where y = 0;

/* 1 がかえるので互いに素 */

一応チェックした

Python 3.7.3 (default, Nov 15 2019, 04:04:52) 
[Clang 11.0.0 (clang-1100.0.33.16)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import math
>>> math.gcd(4563132817,31176473253)
1