約分、素因数分解、素数判定
この３つは実質同じことをする。
ある数について、約数があるかどうかを確かめる。
たとえば、「3007/1067 という分数を約分しなさい」という問題。
パっとみ、割れる数が思いつかない。2, 3, 5あたりはダメ。
すぐにできる約数を見つける方法は、
末尾が偶数... 2
各桁の数を足すと３の倍数... 3
末尾が5か0... 5
そして、２桁だったら素数は列挙してもそんなに時間はかからない。
2, 3, 5, 7, 11, 13, 17, 19, 23,
くらいまではすぐ出る。
29, 31, 37, 41, 43, 47, 53,
この辺から怪しくなってくるか
でも２桁だったら、「素数を列挙してその中にあるか」ではなく、
いくつかの数で割ってみればわかる。１分もかからないだろう。
また、桁数は１０桁とか２０桁とか、「どんな桁数であっても使える素数判定法」を見つけようというのでもない。
まあ、４、５桁くらい。
先ほど例にあげた、3007, 1067 といったような数字で使える、そんなに厳密でなくてもいい方法。
この例では、２つの数字がともに末尾が7となっている。
もしこれらの数字に約数があるならば、２つの数値をかけて結果の末尾（１の位）が7になる数字、ということである。
それはどういう数かと考えて、まず思ったのは、「末尾が7である数と、末尾が1である数の積」である。そして、これだけだと思った。
しかし、それだけではなく、3x9=27 でもある。
ただ、これだけわかればだいぶ楽だ。
3007について。
2, 3, 5 では割れないことはわかっている。
7は、微妙だが割ってみればすぐわかる。割れない。
8, 9, 10 はそれぞれその約数で割れないのですでに対象外。
２桁になっていく。
４桁の数で、「約分しなさい」という問題だから、おそらく２桁x２桁になるのだろう。
候補は下１桁が1, 3, 7, 9
これくらいなら順番に割ってもよさそうだが、
目的はこの問題を解くことではなく簡易的でもいいから判定法を見つけることなので、
もう少し考える。
3007という数の大きさ。
3000は、10x300, 15x200, 30x100 などである。（ほかにもあるが、たとえば。）
ここに登場する、10, 15, 30, 100, 200, 300 などをいじって、
先ほど候補として絞った「下一桁が1と7、あるいは3と9」にしたらどうだろうか？
10x300→ 11x299, 13x299, 17x291
15x200→13x209, 17x191, 19x193
30x100→31x97, 33x99, 29x93
適当にやっただけなので、ざっと見ると
13x209, 29x93は3000に満たないので除外
11x299, 13x299, 17x291
17x191, 19x193
31x97, 33x99
13x299は明らかに大きい
19x193も大きい
33x99も大きい
11x299, 17x291
17x191, 31x97,
おっと、末尾が7にならないのが混じっていた。
17x291, 17x191, 31x97,
17x291=17x(300-9)=5100-153
17x191=17x(200-9)=3400-153
31x97=31x(100-3)=3100-93=3007 ... これ！
1067は...
同様にやってもいいのだが
すでに3007=31x97が判明しているので
どっちかで割れるであろう。
31x37かな
(30+1)x37 ... 違う
31x27=(30+1)x27=810+27... 違う
97x11は...
(100-3)x11=1100-33=1067... これ！
ちなみに1067の方を先にやった場合の候補は
1067だと、1000との差がやや大きい。
1000=10x100, 20x50, 500x2, 330x3+α, 250x4
で、末尾が7になるから
11x97, 21x47,
500x2, 330x3, 250x4は除外
もう答えを知ってるから 11x97がすぐ出てきちゃったけど...
