素因数分解の定石を整理する
素因数分解がガチプロスポーツになってしまったので、初心者の私は定石を明文化することにしました。
また、これらの定石で対応できる数の割合もプログラミングを使って調べました。
対照実験: 全ての数を素数とみなす
問題として出された数をそのまま返す方法です。実用性は全くありませんが、対照実験として割合を掲載します。
正しく判定できる割合
4桁: 1061/9000(11.8%)
5桁: 8363/90000(9.3%)
6桁: 68906/900000(7.7%)
定石1: 2,3,5の倍数を調べる
非数学徒にもよく知られた方法です。2と5の倍数は1の位、3の倍数は桁ごとの和で調べられます。
これだけで48以下の数は全て正しく判定できるだけでなく、4桁であれば判定の精度は50%を超えます。
正しく判定できる割合
4桁: 5067/9000(56.3%)
5桁: 38253/90000(42.5%)
6桁: 303230/900000(33.7%)
定石2: 7,11,13の倍数を調べる
素数大富豪プレイヤーにはよく知られた方法ですが、1001=7×11×13なので与えられた数を1001で割ることで7,11,13の倍数判定を同時に行うことができます。
289=17^2未満は正しく判定できます。
この時点で6桁の数でも50%以上を正しく判定できます。
正しく判定できる割合
4桁: 7314/9000(81.3%)
5桁: 57970/90000(64.4%)
6桁: 460038/900000(51.1%)
定石3: 23,29の倍数を調べる
17,19よりも計算が簡単なのでこちらを先に書きます。23×29×3=2001であることを利用します。
正しく判定できる割合
4桁: 7700/9000(85.6%)
5桁: 63245/90000(70.3%)
6桁: 509869/900000(56.7%)
定石4: 17,19の倍数を調べる
17×19×3=1000-31であることを利用します。少し面倒です。しかし、これでついに4桁の割合が90%を超えます。
正しく判定できる割合
4桁: 8405/9000(93.4%)
5桁: 71817/90000(79.8%)
6桁: 589097/900000(65.5%)
定石5: 平方数を足すと平方数
平方数を足して平方数になるかを調べます。もしなる場合は、2乗-2乗の形にできるので因数分解できます。
元の数自体が平方数である場合もここに含まれます。
正しく判定できる割合: 0^2から10^2まで調べた場合
4桁: 8605/9000(95.6%)
5桁: 74250/90000(82.5%)
6桁: 605776/900000(67.3%)
4桁の判定失敗が395個にまで減りました。
定石∞: ルックアップテーブル
せっかくなので、残りの395個を分類して全列挙してみましょう。
途中で諦めるパターン
3286=2×1643(実際には2×31×53)のように、395個の中には小さい4桁の素因数分解で失敗するケースが重複して数えられているものがあります。
このようなパターンは116個あり、取り除いた残りは279個です。
実は自明なパターン
ここまで来て見逃しているパターンがありました。それは、101の倍数です。
279個のうち101の倍数は12個あり、取り除いた残りは267個です。
2桁の掛け算
残りは全て2桁×2桁か2桁×3桁の強者ぞろいです。2桁は31から83まで多岐にわたり、覚えるしかありません。
以下にリストを示します。覚えられるもんなら覚えてみやがれください。
31×53=1643 31×59=1829 31×61=1891 31×67=2077 31×71=2201 31×73=2263 31×79=2449 31×83=2573 31×89=2759 31×97=3007 31×103=3193 31×107=3317 31×109=3379 31×113=3503 31×127=3937 31×131=4061 31×137=4247 31×139=4309 31×149=4619 31×151=4681 31×157=4867 31×163=5053 31×167=5177 31×173=5363 31×179=5549 31×181=5611 31×191=5921 31×193=5983 31×197=6107 31×199=6169 31×211=6541 31×223=6913 31×227=7037 31×229=7099 31×233=7223 31×239=7409 31×241=7471 31×251=7781 31×257=7967 31×263=8153 31×269=8339 31×271=8401 31×277=8587 31×281=8711 31×283=8773 31×293=9083 31×307=9517 31×311=9641 31×313=9703 31×317=9827
37×59=2183 37×61=2257 37×67=2479 37×71=2627 37×73=2701 37×79=2923 37×83=3071 37×89=3293 37×97=3589 37×103=3811 37×107=3959 37×109=4033 37×113=4181 37×127=4699 37×131=4847 37×137=5069 37×139=5143 37×149=5513 37×151=5587 37×157=5809 37×163=6031 37×167=6179 37×173=6401 37×179=6623 37×181=6697 37×191=7067 37×193=7141 37×197=7289 37×199=7363 37×211=7807 37×223=8251 37×227=8399 37×229=8473 37×233=8621 37×239=8843 37×241=8917 37×251=9287 37×257=9509 37×263=9731 37×269=9953
41×67=2747 41×71=2911 41×73=2993 41×79=3239 41×83=3403 41×89=3649 41×97=3977 41×103=4223 41×107=4387 41×109=4469 41×113=4633 41×127=5207 41×131=5371 41×137=5617 41×139=5699 41×149=6109 41×151=6191 41×157=6437 41×163=6683 41×167=6847 41×173=7093 41×179=7339 41×181=7421 41×191=7831 41×193=7913 41×197=8077 41×199=8159 41×211=8651 41×223=9143 41×227=9307 41×229=9389 41×233=9553 41×239=9799 41×241=9881
43×67=2881 43×71=3053 43×73=3139 43×79=3397 43×83=3569 43×89=3827 43×97=4171 43×103=4429 43×107=4601 43×109=4687 43×113=4859 43×127=5461 43×131=5633 43×137=5891 43×139=5977 43×149=6407 43×151=6493 43×157=6751 43×163=7009 43×167=7181 43×173=7439 43×179=7697 43×181=7783 43×191=8213 43×193=8299 43×197=8471 43×199=8557 43×211=9073 43×223=9589 43×227=9761 43×229=9847
47×71=3337 47×73=3431 47×79=3713 47×83=3901 47×89=4183 47×97=4559 47×103=4841 47×107=5029 47×109=5123 47×113=5311 47×127=5969 47×131=6157 47×137=6439 47×139=6533 47×149=7003 47×151=7097 47×157=7379 47×163=7661 47×167=7849 47×173=8131 47×179=8413 47×181=8507 47×191=8977 47×193=9071 47×197=9259 47×199=9353 47×211=9917
53×79=4187 53×83=4399 53×89=4717 53×97=5141 53×103=5459 53×107=5671 53×109=5777 53×113=5989 53×127=6731 53×131=6943 53×137=7261 53×139=7367 53×149=7897 53×151=8003 53×157=8321 53×163=8639 53×167=8851 53×173=9169 53×179=9487 53×181=9593
59×83=4897 59×89=5251 59×97=5723 59×103=6077 59×107=6313 59×109=6431 59×113=6667 59×127=7493 59×131=7729 59×137=8083 59×139=8201 59×149=8791 59×151=8909 59×157=9263 59×163=9617 59×167=9853
61×83=5063 61×89=5429 61×97=5917 61×103=6283 61×107=6527 61×109=6649 61×113=6893 61×127=7747 61×131=7991 61×137=8357 61×139=8479 61×149=9089 61×151=9211 61×157=9577 61×163=9943
67×89=5963 67×97=6499 67×103=6901 67×107=7169 67×109=7303 67×113=7571 67×127=8509 67×131=8777 67×137=9179 67×139=9313 67×149=9983
71×97=6887 71×103=7313 71×107=7597 71×109=7739 71×113=8023 71×127=9017 71×131=9301 71×137=9727 71×139=9869
73×97=7081 73×103=7519 73×107=7811 73×109=7957 73×113=8249 73×127=9271 73×131=9563
79×103=8137 79×107=8453 79×109=8611 79×113=8927
83×107=8881 83×109=9047 83×113=9379
