数学の質問です。例えば18の約数を調べる際、18と言う数は小さいので特に頭で考えなくても、1、

数学の質問です。

例えば18の約数を調べる際、18と言う数は小さいので特に頭で考えなくても、
1、2、3、6、9、18と分かります。
しかし645とか1230(適当に設定しました)とかの3桁を超えるような大きい数字の約数を調べる際はどのような方法で調べていくのでしょうか？
御回答お待ちしてます。

No.8 ベストアンサー 回答者： ORUKA1951 回答日時： 2016/02/26 21:15

例を挙げたほうがわかりやすい

645
　一目見て 5で割れることはわかる。・・・1の位が0か5
5)645
　129

129も一目見て3で割れることがわかる・・・1 + 2 + 9 = 12 が3の倍数
3) 129
　　43
43は、素数　6×6 = 36 、7×7=49 6や7で割り切れない
★今まで計算してきた数、ここでは5より大きい数をチェックする。6× 6 = 36、7×7= 49・・49>43なのでこれ以上大きな数は調べなくてよい。

1230
　一目見て 5で割れる
5) 1230
　　246

246
　一目みて、3で割れる
3) 246
　　82

82
　一目見て2で割れる・・・１の位が偶数
2) 82
　 41

よって、645 = 3×5×43、1230=2×3×5×41
偶然に素数は一個ずつしかないので、
約数の数は、
645は、1と645を除いて、₃C₁ + ₃C₂ = 6通り
1230は、1と1230を除いて、₄C₁ + ₄C₂ + ₄C₃ = 4 + 6 + 4 = 14通り
約数が重複するときは指数で計算すると楽
約数 - Wikipedia( https://ja.wikipedia.org/wiki/%E7%B4%84%E6%95%B0 … )

結局、コツコツと数えるには代わりないが、9桁(999999999)でも、√(10¹⁰) = 31622 までの素数を調べればよい・・・とはいっても、それまでに割れる数が見つかれば急激に調べる個数は少なくなる。
　例えば、111111だと
3で割れるので37037
　これは、7で割れるので5291
　　これは、11で割れるので、481　　11²=121<481 なので後少し
　　　これは、13で割れるので、37　　13²=169 >37　なのでこれ以上は計算しなくてよい

No.7 回答者： tekcycle 回答日時： 2016/02/26 20:38

まずは1の位を見ますかね。

５なら5の倍数だし、0なら10の倍数。偶数なら2の倍数です。
645なら６＋４＋５、1230なら１＋２＋３＋０を計算して、それが３の倍数なら、元の数字も３の倍数です。
そうやって素因数分解していきます。
ただ、221とか1219は気がつかないだろうと思います。
221だと、１５×１５＝２２５ですから、約数があるとすれば、１５より小さい物があるはずだ、と考えて、１５より小さい素数で割ってみます。

No.6 回答者： orosiajin 回答日時： 2016/02/26 12:09

素因数分解を利用するの補足。

約数は順番に拾うしかないので、自分の好きな方法でみなさん求めていると思います。


６４５の場合　　　３×５×４３＝６４５
約数の個数は指数に１を加えた数を掛けたものです
（１＋１）×（１＋１）×（１＋１）＝８個


さて、この８個を拾う方法は

　３）６４５
　５）２１５
　　　　４３
まず１と６４５、３、５，２１５、４３を拾います
次に４３の相方は上のはしご算の割る数を拾って掛けたもの３×５、つまり１５
最後に一番下のはしごの数を（この場合は４１）、残りの掛け合わせていない３と掛けます　３×４３＝１２９
１、３、５、１５、４３、１２９、２１５、６４５ 計８個です。



１２３０の場合　　　　２×３×５×４１＝１２３０
指数は１、１、１、１、なので約数の個数は
（１＋１）×（１＋１）×（１＋１）×（１＋１）＝１６個

１６個を拾う方法は

３）１２３０
５）　４１０
２）　　８２
　　　　４１
まず１、２、３、５、４１、８２、４１０、１２３０を拾い、

４１の相方は上のはしごの ２×５×３＝３０

８２の相方は上のはしごの ３×５＝１５

次にに掛け合わせていない数同士を掛けます。
４１×５＝２０５、４１×３＝１２３、４１×３×５＝６１５、４１×2×３＝２４６

最後にはしごの割る数、２、５、３で掛け合わせていないものも掛けます　２×５＝１０、２×３＝６

１、２、３、５、６、１０、１５、３０、４１、８２、１２３、２０５、２４６、４１０、６１５、１２３０ 計１６個



もっと簡単なのは、素因数分解で割る順番を変えていく方法

３）１２３０
５）　４１０
２）　　８２
　　　　４１

割る順番を変えます
５）１２３０
２）　２４６
２）　１２３
３）　　４１

また割る順番を変えます
２）１２３０
３）　６１５
５）　２０５
　　　　４１
　
はしご算に現れたすべての数をまず拾って　１、２、３、５、４１、８２、１２３、２０５、２４６、４１０、６１５、１２３０　　１２個

はしごの割るほうの数同士で掛けます　２×３＝６、２×５＝１０、２×３×５＝３０、３×５＝１５　4個


合計１６個です。

No.5 回答者： orosiajin 回答日時： 2016/02/26 01:30

素因数分解を利用します

No.4 回答者： rabbit_cat 回答日時： 2016/02/25 09:56

順番に試していくしかないです。

与えられた数の約数を順番に試すことなく見つけられる方法は、（少なくとも今は）見つかっていません。
もし、こういう方法が見つかれば、インターネットで使われている暗号化技術の多くが無効化されることになります。
あるいは、最近話題のビットコインを自由に無限に作り出して大金持ちになることもできます。

No.3 回答者： tknakamuri 回答日時： 2016/02/24 13:47

√(645)≒25.4 だから、25以下の

素数で割れるかどうか、考えればよい。

2, 3, 5, 7, 9, 11, 13, 17, 19, 23

試すのはこれだけです。

同様に

√(1230)≒35.1

試すのは

2, 3, 5, 7, 9, 11, 13, 17, 19, 23、29、31

割って小さくなった数を更に割るのにも
同じ手法が使えます。

No.2 回答者： t_fumiaki 回答日時： 2016/02/24 13:37

√645とか√1230を大雑把に求める。

√645≒26 √1230≒36
２６までや36までの素数で割ってみる。
割り切れた数を書き出す。商に対して同じ事を繰り返す。割り切れなくなったら終わり。
書き出した数を組み合わせて掛け算したものが約数

●645を例にとると
そこまでの素数は2,3,7,11,13,17,19,23,29
これで割ってみる

645 ÷ 3 商：215
215 ÷ 5 商：43
43 43は2,3,7,11,13,17,19,23,29で割れないので終わり。
約数は3,5,43
と3,5,43を組あわせて掛けた数3×5, 3×43, 5×43
1と自分も含めると約数は1, 3, 5, 15, 129, 215, 645

●1230を例にとると
そこまでの素数は2,3,7,11,13,17,19,23,29,31,
1230 ÷ 2 商：615
615 ÷ 3 商：205
205 ÷ 5 商：41
41 ここで終わり。

約数は1, 2, 3, 5, 41, 2×3, 2×5, 2×41, 3×5, 3×41, 5×41, 1230
=1,2,3,5,41,6,10,82,15,123,205,1230

No.1 回答者： m-jiro 回答日時： 2016/02/24 11:16

小生のやり方

１．偶数ならば２で割る。必ず割ることができる。
２．１の桁が０か５ならば５で割る。これも必ず割ることができる。
３．３か７で割ってみる。割り切れたら採用。
４．それでも１１とか１３、１７、１９等（いずれも素数）で割れることがあるのでこれも試みる。
５．以上を繰り返す。最後が素数になったら終了。

４．で素数は無限にあるのでどこまでするかは根気と努力（？）ということになりますが、元の数の半分まですれば十分です。素数は５０ぐらいまでは覚えておくとよいですね。
これで余程意地悪な問題でない限りほぼ大丈夫です。

例　６４５は１の桁が５なので５で割ることができる。
　　６４５÷５＝１２９　　１２９は３の倍数かな？　割ってみる。
　　１２９÷３＝４３　　３で割りきれた。４３は素数なので終了。
つまり　６４５＝５×３×４３　となり、約数は５、３、４３の３個。

３．で元の数が３で割れるかどうかは、各桁の数字を全部足して３の倍数になれば元の数は３の倍数。
　　例　１２３０　→　１＋２＋３＋０＝６　６は３の倍数なので１２３０は３の倍数。
　　　これも知っておくと便利。