素因数分解の難度を考える　｜基礎計算研究所

　約分の最後の頼みの綱は、素因数分解です。

　この稿では、素因数分解の「難度」を決める要素を考えてみます。（中３以降の因数分解でも役に立つはずです）

前提：素因数分解の一意性

　分解の順番がちがうと，答えがちがうのでは，と思ってしまう人もいるかも知れませんが，素因数分解の一意性といって、どんな順番で分解していっても、最後は同じことになります（→Wikipedia）。このことは，中学校の教科書では「途中の順序は変わっても、同じになります」（啓林館）「どんな順序で行っても同じ結果になる」（東京書籍・学校図書）と表現されています。

１．かけ算分解の見つけやすさ

　素因数分解は、小さい数から順に試行錯誤的に割っていくのが確実なアルゴリズムです。そのためコンピューターを使っても計算に時間がかかる、と言われています。
　ただ、実際に算数や数学で扱う数の範囲では「何でわれるか？」をヒューリスティックに見つけていきます。できるだけ小さな数はもう少し簡略に判定できるわけです。
　約数を見つけるヒューリスティックの方法としては、分数の約分と同様「末尾に注目する」「九九を活用する」「各位の和を活用する」あたりがあります。ぞろ目などの「数の並び」に注目する方法もあるでしょう。
　その数が，これらいくつかある方法であてはまるかどうかに注目していくことが、素因数分解の最初の手続きとなるわけです。

◎　下１桁の注目
　　①１０^nの倍数
　　②５の倍数
　　③２の倍数（＝偶数）
◎　九九
　　④奇数×奇数
⑤　各位の和＝３の倍数・９の倍数
◎　数の並び
　　⑥ぞろめ（７７）
　　⑦各位の数がすべて２～４の数でわれる（６９、６３９など）
　　⑧どこかの位で区切るとそれぞれが何かの倍数になっていることがわかる（217、3926など）

　その数をどのように分解しようと，いちばんの問題は２と５でわった「残り」の因子の扱いです。５の倍数以外の奇数の素因数分解は，手がかりを見つけるのが難しくなります。それは、スタートの数の大きさには依存しません。例えば６８のように、２や５でわった残りの因数は１７です。１７が出てきたときに壁にぶつかります。
　スタートの数がもともと持っている「宿命」のようなもの、と考えることができます。ある自然数の２と５以外の素因数を全てかけた数をここではF数と呼んでおきます。（宿命Fateから。ちょっと数秘術っぽいですが）

　上のやり方でいうと、九九・各位の和・数の並びが活用できるかどうかが鍵になります。これをもとに、いくつかのカテゴリーに分けてみます。
　カテゴリー１や２は、分解の途中で九九が活用できる数でもあります。九九の中にある数を特に太字にしておきます。

カテゴリー１　Ｆ数（２と５の素因数を割りつくした数）が１桁の数（１，３，７，９）になる
※2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,24,25,28,30,32,35,36,40,45,48,50,56,60,64,70,72,75,80,90,96,100,112,120,125,128,140,144,150,160,175,180,192,200,224,225,240,250,256,280,288,300,320,350,360,375,384,400,448,450,480,500,・・・）

カテゴリー２　Ｆ数（２と５の素因数を割りつくした数）が九九にある２桁の奇数（21，27，49，63，81）になる
※21,27,42,49,54,63,81,84,98,105,108,126,135,162,168,196,210,216,245,252,270,315,324,336,392,405,420,432,490,・・・

　ここで、Ｆ数にさらに３で割りきれるものをわった数Ｇ数も導入しておきます。3の倍数判定は比較的容易なので。

カテゴリー３　Ｇ数（２と３と５の素因数を割りつくした数）が、１か７か49になる
※147,189,243,294,378,441,486,・・・

カテゴリー４　Ｇ数が上記以外の奇数
4-１　11以上の素数を１つ含む
4-1-1　２桁以上の素数（11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,・・・）、
4-1-2　合成数
22,26,33,34,38,39,44,46,51,52,55,57,58,62,65,66,68,69,74,76,78,82,85,86,87,88,92,93,94,95,99,102,104,106,110,111,114,115,116,117,118,122,123,124,129,130,132,134,136,138,141,142,145,146,148,152,153,155,156,158,159,164,165,166,170,171,172,174,176,177,178,183,184,185,186,188,190,194,195,198,201,202,204,205,206,207,208,212,213,214,215,218,219,220,222,226,228,230,232,234,235,236,237,244,246,248,249,254,255,258,260,261,262,264,265,267,268,272,274,275,276,278,279,282,284,285,290,291,292,295,296,297,298,302,303,304,305,306,309,310,312,314,316,318,321,325,326,327,328,330,332,333,334,335,339,340,342,344,345,346,348,351,352,354,355,356,358,362,365,366,368,369,370,372,376,380,381,382,386,387,388,390,393,394,395,396,398,402,404,408,410,411,412,414,415,416,417,422,423,424,425,426,428,430,435,436,438,440,444,445,446,447,452,453,454,456,458,459,460,464,465,466,468,470,471,472,474,475,477,478,482,485,488,489,492,495,496,498,・・・
4-２　それ以外（素因数に7を３つ以上含む、または7以上の素因数を２つ含む）
※７７（７＊１１）９１（７×１３），１１９（７＊１７），１２１（１１＊１１），１３３（７＊１９），１４３（１１＊１３），１５４（２＊７＊１１），１６１（７＊２３），１６９（１３＊１３），１８２（２＊７＊１３），１８７（１１＊１７）・・・

２．何回分解するか？

　素因数分解が何回で終わるかは、素因数がいくつあるか、素因数の数によります。例えば12だと

12＝2＊2＊3

で３個ある、という意味です。

　重複を含めた素因数の総数をΩで表すことにします（→Wikipedia）。
　すると、素因数分解の回数は（Ω－１）回とあらわすことができます。分解の回数はΩによって決まり、どのように途中で分解しようと変わりません。

　これは、Ωが大きいほど素因数分解の回数が多くなり、それだけ手間や計算が増える、ということになります。

【追補】何通りに分解できるか？

　繰り返しになりますが、初歩的な素因数分解は上の①～⑧などの方法を当てはめてみるプロセスを踏みます。分解の選択肢が多い方が、そのどれかを思いつけばいいので、その分かけ算分解を見つけやすくなると考えるのは、妥当でしょう。

　例えば16と36はいずれも同じΩ＝4の数ですが、その分解の組合せは、次のように16だと２通り、36だと４通りになります。

　あまり小難しい数式を出すのは本意ではありませんが、こればかりは文章で説明するよりも、数式を示してしまった方がよいのいで、公式を出しておきます。

　k，l，m…は、素因数分解を累乗の積で表したときの各素因数の累乗の指数、上だけあるかっこは整数切り上げをあらわしています。１×Nという組合せは素因数分解には不要ですので，１をひいています。

　「分解の組合せ数」が多ければ分解の組み合わせの選択肢も増え、思いつきやすさも増えると考えられます。そのため、素因数分解のとっかかりやすさの目安として使うことにします。

３．数の大きさ・桁数　

　あと、桁数も計算の面倒さ決める要因として挙げておきます。÷２や÷５をするにしても、÷３をするにしても、「筆算」の稿で見たとおり、計算回数は桁数に依存します。

　また一般に数が大きくなれば、Ωが大きくなったり、素因数に大きな素数を含む可能性も増えたりするために、素因数分解が面倒になる傾向がある，ということも言うことができます。これも桁数を１つの指標にする根拠です。

　ただし、数の大小が単純に大きい数の方が素因数分解が難しい，という意味ではありませんので注意してください。３６０と１８２では、難しさは約半分、ということにはなりません。

　以上の分析に基づき、具体的に次の稿でまとめてみた。