Project Euler Problem4-6

projecteuler.net

数学パズルをプログラミングで解くサイト、Project Eulerの不定期連載です(一応続いた...)
解法ありにつきネタバレ注意!!!

目次

• 4. Largest palindrome product
• 5. Smallest multiple
• 6. Sum square difference

4. Largest palindrome product

Problem 4 - Project Euler

2つの3桁の整数を掛け算してできる回文数のうち、最大なものを求めよ。
競プロでよく出てくる回文判定と全探索を使えばいける。
(3桁だから全探索で行けるんだろうけど、桁数増えたら計算量工夫しないと爆死)

# 2つの3桁の整数を掛け算してできる回文数のうち、最大なものを求めよ

# 回文になっているか比較。数字を文字として受け取り、反転させたものと比較
def palindrome(num):
    num = str(num)
    if num == num[::-1]:
        return True


def main():
    ans = 0
    for i in range(100, 1000):
        for j in range(100, 1000):
            num = i * j
            if palindrome(num) and num > ans:
                ans = num
                ans_i = i
                ans_j = j
    print(ans, str(ans_i) + '*' + str(ans_j))
    # 906609, 913*993


if __name__ == "__main__":
    main()

5. Smallest multiple

Problem 5 - Project Euler

1から20までの数すべてで割り切れる最小の正の整数は？と聞かれているが、
1から20までの最小公倍数を求める問題に置換できる。
手持ちの最小公倍数を求めるライブラリを使って実装。

import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


def main():
    ans = 1
    for i in range(2, 20):
        ans = lcm(ans, i)
    print(ans)
    # 232792560


if __name__ == "__main__":
    main()

6. Sum square differencer

Problem 6 - Project Euler

最初の100個の自然数を2乗した数の和と最初の100個の自然数の和の2乗の差を求めよ
もうやるだけ。リスト内包表記を使って高速にリストを生成する。

num = [i for i in range(1, 101)]
double = sum(num) ** 2
num_double = [i**2 for i in range(1, 101)]
sum_n = sum(num_double)

print(double - sum_n)
# 25164150

また3問くらい解けたら書くかな。