|
そういう事情でしたか。
その点説明があれば、回答も違っていたのですが...
電卓使用可という条件であれば、以下の方法で少し粘れば素因数分解できます。
まず、因数分解の公式に以下のようなものがあります。
x^2-y^2 = (x-y)(x+y)
素因数分解したい数をNとします。
このとき、x^2-y^2 = Nを満たす、x,yを見つけることができれば、
N=(x-y)(x+y)と因数分解することが可能になります。
では、どうやって、x,yを見つけるかというと
N=58055449とします。このルートを計算すると（計算機で)
√58055449 = 7619.44...
x^2-y^2=Nとなるようなx,yを探しているわけなので、xの候補として、
√Nよりも大きな整数が必要なのは分かりますね。
7620が√Nより大きな一番小さな整数なので、これが最小のx候補です。
で、x^2-Nを計算して、その√を計算したら整数になるような値が見つかれば、
そこで、x,yが見つかり、N=(x-y)(x+y)と素因数分解できます。
7620で計算すると、
7620^2-58055449 = 8951
√8951 = 94.609...
なので、x候補として7620は不適です。この場合、x=7621, 7622, ...と当てはめて
行くことになります。
しかし、これではなかなかx,yの候補は見つかりません。
そこでもう少し考えます。
ある整数の２乗を考えると、1の位はいくつになるでしょうか。
1^2 = 1
2^2 = 4
3^3 = 9
4^2 = 16... つまり6
5^2 = 25...つまり5
6^2 = 36...つまり6
7^2 = 49...つまり9
8^2 = 64...つまり4
9^2 = 81...つまり1
10^2 = 100 ... つまり0
11以降を考えると、上記の繰り返しであることが分かります。
平方数の最後の桁は、元の数の1の位の数によって決まります。
これから、平方数になるには1の位は0,1,4,5,6,9の場合だけ
であることがわかりますね。
つまり、x^2-Nの1の位は1,4,5,6,9または0でなければならないことが分かります。
Nの1の位は9なので、x^2の1の位は0,3,4,5,8または9でなければなりません。
x^2も平方数なので、x^2としてありえるのは0,4,5,9で終わる場合に少し絞れます。
よってxの1の位として1,4,6と9は除外できます。
以降
x=7622,7623,7625,7627,7628,7630,7632,7633,7635,7637,7638,7640,7642,
そして、
x = 7643 のとき、（15回目の計算)
7643^2 - 58055449 = 360000
√360000 = 600
N = 50855449 = (7643-600) * (7643+600) = 7043 * 8243
と分解できます。
後は7043と8243がいずれも素数であることを確認できたら、素因数分解が完了します。
この方法はフェルマーという数学者が最初に実施したことから、フェルマーの方法
と呼ばれる素因数分解の方法です。
これを機にアルゴリズムの重要性と勉強の重要性に気付けばいいと思います。
|
