Project Euler 問題4 「2つの3桁の数の積である最大のパリンドローム数」

問題

2つの３桁の数を掛け合わせて得られる最大のパリンドローム数（前から読んでも後ろから読んでも同じ数）を求めよ。

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

コード①

#　２つの因数を大きいもの同士から掛け合わせていく　->　パリンドロームか調べる.
#  最初に出てきたパリンドローム数が最大とは限らないので注意.

#　min, max = 因数の最小、最大
def getLargestPalindromicMultiple(min, max):
  largestMultiple = 0  # 最大のパリンドローム数を保存しておくための変数
  for x in range(max, min, -1):
    for y in range(max, min, -1):
      multiple = str(x * y)

      # 積の桁数が奇数の場合
      if len(multiple) % 2 != 0:
        halfLength = int((len(multiple)+1)/2)
        if multiple[0:halfLength] == multiple[::-1][0:halfLength] and int(multiple) >= largestMultiple:
          largestMultiple = int(multiple)
        else:
          continue
      # 積の桁数が偶数の場合
      else:
        halfLength = int(len(multiple)/2)
        if multiple[0:halfLength:1] == multiple[::-1][0:halfLength] and int(multiple) >= largestMultiple:
          largestMultiple = int(multiple)
        else:
          continue
  return largestMultiple

largestPalindromic = getLargestPalindromicMultiple(100, 999)
print(largestPalindromic)

コード②

# パリンドローム数を作る -> ２つの三桁の因数に分けられるか調べる.

import math

# max = パリンドローム数の左半分の最大, digit = 因数の桁数
def getLargestPalindromicMultiple2(max, digit):

  # パリンドローム数が持つべき最小の因数
  minFactor = 10**(digit-1)

  #　桁数が偶数（977->977779）と桁数が奇数(977-> 97779)の場合を両方調べる（今回の問題では無くてもいい）
  for round in ['even', 'odd']:

    for num in range(max, minFactor, -1):

      # パリンドローム数を作る
      if round == 'even':
        palindromic = int(str(num)+str(num)[::-1])
      else:
        palindromic = int(str(num)[0:-1]+str(num)[::-1])

      #　因数を初期化
      factor = minFactor

      # パリンドローム数が因数で割り切れて、なおかつ割った後の数が定められた桁数の場合パリンドローム数を返す
      while(factor <= math.sqrt(palindromic)):
        if palindromic % factor == 0 and len(str(int(palindromic/factor))) == digit:
          return palindromic
        else:
          factor += 1

# 999^2 = 998001以下の最大のパリンドローム数は997799なのでmaxは997
largestPalindromic2 = getLargestPalindromicMultiple2(997,3)
print(largestPalindromic2)

コード②の方が早くてコードもスッキリしてる印象

Pythonで文字列を逆向きにして部分的に切り取る方法について

ややこしいので一旦[::-1]で逆向きにしてから切り取るのがおすすめ

# nohtyという文字列を切り取る
>>> str = 'python'
>>> str[::-1]
'nohtyp'
>>> str[::-1][:-1]　<-　おすすめ
'nohty'
>>> str[-1:0:-1]
'nohty'