>>39

>>そのやり方でも因数分解するんですか
そうです。

>>難しさは同じなんでしょうか
一般に、ある(巨大な)自然数ｎを因数分解をしないで平方数の差で全ての表し方で表すことは、ｎを素因数分解することよりも難しい(計算量が多い)
なぜなら、ｎを素因数分解するには√ｎまでの素数でｎを割ってみればいいが、一方ｎを平方数の差で全ての表し方で表す場合(大雑把に見積もって)ｎの約半分以下の2つの自然数の組み合わせを考えるので(n/2)^2の計算量が必要となるからである。

ものすごく大雑把に例えれば、10001という自然数が与えられた時
素因数分解するには多くて100回の計算が必要
平方数の差で全ての表し方で表す場合には多くて25000000回の計算が必要となる。

ただし、平方数の差で全ての表し方で表す場合に、もっと楽な画期的な計算方法が見つかれば計算量は少なくなるかもしれない。