クエリで Project Euler Problem 3

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

【お題】

Problem 3。

Problem 3 「最大の素因数」 †
13195 の素因数は 5, 7, 13, 29 である.

600851475143 の素因数のうち最大のものを求めよ.

【環境】

SQLServer SQLCMD
2017 14.0.1000.169

設定はデフォルト。

【クエリ】

普通に考えたら素因数分解だよな。というか、それ以外自分の頭では思いつかなかった。
実装例は以下。

DECLARE @Num    DEC(12, 0) = 600851475143;

;WITH [CTE_Calc]([被除数], [除数], [剰余]) AS (
    SELECT
          @Num
        , 2
        , CONVERT(DEC(12, 0), @Num % 2)
    UNION ALL
    SELECT
          CONVERT(DEC(12, 0), [被除数])
        , [除数]
        , CONVERT(DEC(12, 0), [被除数] % [除数])
    FROM (
        SELECT
              IIF([剰余] = 0, [被除数] / [除数], [被除数])
            , IIF([剰余] = 0, [除数], [除数] + 1)
        FROM [CTE_Calc]
    )t([被除数], [除数])
    WHERE   [被除数] > 1
)
SELECT MAX([除数]) FROM [CTE_Calc]
WHERE   [剰余] = 0
OPTION (MAXRECURSION 0)
;
GO

-----------
       6857

(1 行処理されました)

しかも試し割り法。最も単純なアルゴリズムとされているので説明は不要だろう。
最初は 2 で割り続け、割り切れなかくなったら 3 で……と除数を増やしていくだけの簡単なお仕事。

対象の数値が 12桁と比較的大きいので処理時間が心配だったが、蓋を開けてみたら一瞬だった。これで良しとしますか。
先生出番です。