Project Euler 004 / 最大の回文積（Largest palindrome product）

問題概略

3 桁の数の 2 つの積で表される回文数（左右どちらから読んでも同じ値になる数）の最大値を求めよ。

https://projecteuler.net/problem=4

積を作って回文数判定

3 桁の数 , の積を作って で回文判定しました。

    ans = 0

    for i in range(100, 1000):
        for j in range(100, i + 1):
            if str(i * j) == str(i * j)[::-1]:
                ans = max(ans, i * j)
    
    print(ans)

回文数を作って積に分解

次は逆に回文数からはじめます。
は 5 桁で は 6 桁なので，回文数は か の形をしています。次のようにして解きました。

1. この形の数のリストを作る
2. リストに含まれる数 の約数 を求める
3. と が両方とも 3 桁になる がある を抽出
4. その最大値が答え

    from sympy import divisors

    lst = [a * 10001 + b * 1010 + c * 100
           for a in range(1, 10) for b in range(10) for c in range(10)]
    lst.extend([a * 100001 + b * 10010 + c * 1100
                for a in range(1, 10) for b in range(10) for c in range(10)])
    
    def ok(n):
        return [d for d in divisors(n)
                if 100 <= d < 1000 and 100 <= n // d < 1000] != []
    
    print(max([i for i in lst if ok(i)]))

の形の数は 405450 個で， か の形の数は 1800 個です。解法を変えることでデータ数を約 に減らせました。