素因数分解

 投稿者:山中和義  投稿日:2015年 3月10日(火)10時37分42秒
  問題
123456789を因数分解せよ。

類題
□□□□□×□□□□□=123456789

考察
フェルマー法
n=x^2-y^2=(x-y)(x+y)
X=[√n]として、順にx=X+1,X+2,X+3,…で、x^2-nを満たす平方数y^2を求める。
このとき、x+y,x-yがnの因数となる。
(終わり)

答え 筆算による
11111×11111=123454321([√n]に相当する)なので、x+1=11112である。

x=11112のとき、11112×11112=123476544
   123476544
 - 123456789
 -----------
    5) 19755 ←5の倍数判定より
     -------
        3951
 これは、5の倍数でないので、5^2を因数に持たない。これより、平方数にならない。

 補足
 11112×11112は直接計算してよいが、
 x^2と(x+1)^2=x^2+2x+1の関係より、123454321+2×11111+1=123476544と計算できる。
 (終わり)

x=11113のとき、11113×11113=123498769
   123498769
 - 123456789
 -----------
    5) 41980 ←5の倍数判定より
     -------
        8396
 これは、5の倍数でないので、5^2を因数に持たない。これより、平方数にならない。

x=11114のとき、11114×11114=123520996
   123520996
 - 123456789
 -----------
   11) 64207 ←2,3,5,7で割り切れないので
     -------
        5837
 これは、11の倍数でないので、11^2を因数に持たない。これより、平方数にならない。

x=11115のとき、11115×11115=123543225
   123543225
 - 123456789
 -----------
    2) 86436
     -------
    2) 43218
     -------
    3) 21609
     -------
    3)  7203
     -------
    7)  2401
     -------
    7)   343
     -------
    7)    49
     -------
            7
 これより、y=86436=(2×3×7×7)^2=294^2

よって、11115-294=10821、11115+294=11409から、123456789=10821×11409

3の倍数の判定より、10821=3×3607、11409=3×3803から、123456789=3^2×3607×3803


続いて、3607,3803が素数であろことを判定する。
試し割り法
k^2≦mを満たす素数kがmを割り切らないことを確認する。

m=3607のとき、k=3,5,7,…,59で割り切らない。
m=3803のとき、k=3,5,7,…,61で割り切らない。

以上より、求めることができた。
(終わり)


平方数の判定は、√キー付き電卓があると楽ですね。


LET N=123456789
LET X=INT(SQR(N))
DO
   LET X=X+1
   LET Y2=X*X-N
   LET Y=INT(SQR(Y2))
   PRINT X;Y2;Y
LOOP UNTIL Y^2=Y2
PRINT X-Y;X+Y
END


実行結果
11112  19755  140
11113  41980  204
11114  64207  253
11115  86436  294
10821  11409


 

Re: 素因数分解

 投稿者:山中和義  投稿日:2015年 3月12日(木)10時08分33秒
  > No.3604[元記事へ]

> 類題
> □□□□□×□□□□□=123456789

みんな「社会人になると、因数分解することはなくなるね。」
今年卒業する総監督「46,48グループ全員で、恋する...(^^♪」

11111×11111=123454321<123456789<12346×10000より、11111<a<12346
元の数の一の位が9なので、1×9=9、3×3=9、7×7=49より、Aの一の位を1,3,7,9で検証する。

FOR A=11113 TO 12346-1 STEP 2
   LET B=123456789/A
   IF B=INT(B) THEN PRINT A;B
NEXT A
END


別解
総監督「神7にお願い!フライングゲット♪」

a≧bとして、n=abとする。x=(a+b)/2、y=(a-b)/2とおくと、n=x^2-y^2、a=x+y、b=x-y
11111×11111=123454321<123456789<12346×10000より、(11111+11111)/2=11111<x<(12346+10000)/2=11173
平方数を扱う必要があるが、
平方数の一の位は、0,1,4,5,6,9となる
より、いきなり素因数分解する必要はない。

FOR X=11111+1 TO 11173-1
   LET Y2=X*X-123456789
   LET Y=INT(SQR(Y2))
   IF Y*Y=Y2 THEN PRINT X+Y;X-Y
NEXT X
END


みんなで協力(分担作業)して解きました。

 

戻る