素因数分解の暗算高速化

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

方針

簡単に計算できるように, 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倍を足さなきゃいけないので面倒です. 誰かもっと良い方法教えて.

それでは.

Google Code Jam 2011 反省

総括

A -> C -> B の順に解いていった. D はちゃんと読んでないけど, 読んですぐ解けるのを選んでいった.

問題読むのにも時間かかるのでこの方針は間違ってないはず.

Problem A

順調に解け問題無し. 細かい計算をもっと速く実装できるように鍛錬.

Problem C

英語の読み間違いにより時間をロス. 英語をすらすらと読めるようになろう.

素数がらみの問題だと分かったが, 素数生成で手間取る. こういうのは予めメモリサイズや速度を考慮したライブラリを自分で作っておくべき. 去年と同じく Big の方でメモリサイズを考えずにプログラムを走らせ, swap しまくりで遅くなり expired. 無念.

終わってから大きい方の素数について無駄な計算をしていることに気付く. 枝刈りの感覚重要.

Problem B

総当たりっぽかったのでいったん避けたが, やっぱり総当たりしか方法が無さそう. 最初から解けば良かった.

Python で解いていたが, debug に手間取り時間切れ.

追記

他の人のつぶやきを見ていて気付いたこと.

Problem B で総和を何度も求めているが, そこのコスト計算をしてなかった. 範囲を変えて総和を求める場合のチューニング方法を知っておくべき. 先頭からの和を取って事前処理をしておけば, 部分的な総和は O(1) で求まる.

Licenses