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

ある数値が与えられたとき、その数値が17で割り切れるかどうかを判定する必要があるとします。

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

解法のアプローチ：繰り返し減算法

この問題は「繰り返し減算法」と呼ばれる手法で解くことができます。具体的には、数値の末尾の桁を取り出し、残りの数値から「末尾の桁 × 5」を引くという操作を、数値が2桁になるまで繰り返します。最終的に得られた2桁の数値が17で割り切れるなら、元の数値も17で割り切れることになります。

この方法が成り立つ理由は、数値を「10a + b」（aは末尾の桁を除いた部分、bは末尾の桁）と表したとき、「a − 5b」が17で割り切れることと「10a + b」が17で割り切れることは数学的に同値であるためです。

アルゴリズムの手順

• 数値が100以上である間、以下を繰り返します。
  • last_digit := number mod 10（末尾の桁を取得）
  • number := number を10で割った商（末尾の桁を削除）
  • number := number − last_digit × 5
• ループ終了後、number を17で割った余りが0であれば true を返します。

それでは、実際の実装を見てみましょう。

サンプルコード

def solve(number) :
    while(number // 100) :
        last_digit = number % 10
        number //= 10
        number -= last_digit * 5
    return (number % 17 == 0)

number = 99943
if solve(number) :
    print("Divisible")
else :
    print("Not Divisible")

入力

99943

出力

Divisible

コードの解説

このプログラムでは、まず solve() 関数内の while ループで、数値が3桁以上である限り処理を続けます。各ループで末尾の桁を取り出し（number % 10）、数値を1桁短くしてから（number //= 10）、末尾の桁の5倍を引きます。

数値が2桁になった時点でループを抜け、その値が17で割り切れるかどうかを number % 17 == 0 で判定します。99943 の場合、この変換を繰り返すと最終的に17の倍数となるため、「Divisible」と表示されます。

この手法を使うと、大きな数値でも直接割り算を行うことなく、17の倍数かどうかを効率的に判定できます。