クエリで Project Euler Problem 5

3857 ワード
初心者 SQLServer アルゴリズム ProjectEuler SQLServer テキストリンク

【お題】

Problem 5。

Problem 5 「最小の倍数」 †
2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.

では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.

【環境】

SQLServer SQLCMD
2017 14.0.1000.169

設定はデフォルト。

【クエリ】

要は最小公倍数。最小公倍数の基本的な知識は以下。

  • 3個以上の最小公倍数を求める場合はまず最初の 2項の最小公倍数を求め、更にそれと3番目の最小公倍数を求め……を繰り返す
  • 最大公約数から最小公倍数を得ることができる。a、b の最小公倍数 = a * b / (a、bの最大公約数)
  • 最大公約数は ユークリッドの互除法 が鉄板

……なんだけど、今回に限っては単純な試し割法の方がアルゴリズムとしてすっきりする。実装例は以下。

;WITH CTE_LCM(a, b, c) AS (
    SELECT 1, 1, 2
    UNION ALL
    SELECT
          IIF(b % c = 0, b, a)      -- 割り切れたら最小公倍数で置き換える
        , IIF(b % c = 0, b, b + a)  -- 割り切れたら最小公倍数、割り切れなければ 2倍、3倍...としていく
        , IIF(b % c = 0, c + 1, c)  -- 割り切れたら次の値(1加算)
    FROM CTE_LCM WHERE c <= 20
)
SELECT MAX(b) FROM CTE_LCM;
GO

-----------
  232792560

(1 行処理されました)

一瞬で返ってくるし、これで良いのでは。以下答え合わせ。