素因数分解の暗算高速化

誰の役に立つのか, 何の役に立つのか良く分からないが, 中学生くらいのときから数字を見るたびに素因数分解に挑んできた俺が使っている, 暗算で素因数分解をする方法を紹介します.

方針

簡単に計算できるように, 1桁の掛け算と2桁の足し算くらいしか使わないことにします.

11で割る

まず, 一番簡単な11から.

11 = 10 + 1 を利用して, 11の倍数をどんどん引いていきます. 残りが0になったら11の倍数, そうでなかったら11の倍数でない, と分かります.

具体例

135 から始めます.

  1. 135 を 13 と 5 に分解.
  2. 13 - 5 を計算して 8.
  3. 11 で割れないので終了.

簡単ですね.

7で割る

7 * 3 = 21 を利用します.

具体例

1113 から始めます.

  1. 1113 を 111 と 3 に分解.
  2. 111 - 3 * 2 = 105.
  3. 105 を 10 と 5 に分解.
  4. 10 - 5 * 2 = 0. よって7で割り切れる.

色んな数で割る

せっかくなので, 41 くらいまでは揃えてみましょう. そうしておけば, 42^2 = 1764 までの数に出会ったときに素因数分解で困ることは無いです(誰得

3で割る

各桁の数字を足す. 有名なのですぐ分かる.

5で割る

下1桁見れ.

7で割る

既出

11で割る

既出

13で割る

13 * 3 = 39 を利用して,

  1. 下1桁と上の残りに分解
  2. 上の残りに下1桁の4倍を足す

で, 13で割った余りを変えずに数を小さくできる.

17で割る

17 * 3 = 51 を利用して, 下1桁の5倍を上の残りから引けば良い.

19で割る

下1桁の2倍を上の残りに足せば良い.

23で割る

23 * 3 = 69 なので, 下1桁の7倍を上の残りに足す.

29で割る

3倍を足す.

31で割る

3倍を引く.

37で割る

37 * 3 = 111 なので, 11倍を引く. 37の倍数で2桁のものは, 37 と 74 しかないので覚える.

41で割る

4倍を引く.

まとめ

非常に誰得なエントリですが, こういうネタが好きな人が居れば嬉しいです. というか変態です.

43 は素直にやると13倍を足さなきゃいけないので面倒です. 誰かもっと良い方法教えて.

それでは.

Licenses