Pythonで数値が19で割り切れるかどうかを判定する方法

非常に大きな数値が与えられたとき、その数値が19で割り切れるかどうかを判定したいケースがあります。

例えば、入力が 86982 の場合、出力は「Divisible（割り切れる）」となります。

アルゴリズムの考え方：繰り返し加算法

この問題は「繰り返し加算法」と呼ばれる手法で解くことができます。この方法では、数値から末尾の1桁を取り出し、それを2倍した結果を残りの数値に加えるという操作を、数値が2桁になるまで繰り返します。そして最終的に得られた2桁の数値が19で割り切れるかどうかを調べます。

具体的な手順

• 数値が100以上である間（number // 100 が0でない間）、次の処理を繰り返します。
  • last_digit := number mod 10 … 末尾の桁を取り出す
  • number := floor(number / 10) … 末尾の桁を除去する
  • number := number + last_digit * 2 … 末尾の桁の2倍を加算する
• number mod 19 == 0 であれば True を返します。

この手法により、桁数が多くても19による割り切れ判定を効率的に行えます。

実装例

以下のコードを見ると、処理の流れがより理解しやすくなります。

def solve(number) :
   while(number // 100) :
      last_digit = number % 10
      number //= 10
      number += last_digit * 2
   return (number % 19 == 0)
number = 86982
if solve(number) :
   print("Divisible")
else :
   print("Not Divisible")

入力

86982

出力

Divisible