algorithm - 素因数分解による除算性のチェック

Question

整数（たとえばA）の別の整数（たとえばB）による除算性をチェックするために、Bを因数分解し、AがBのすべての素因数で割り切れるかどうかをチェックするアプローチを試しました。しかし、それが正しいかどうかはわかりませんか？何ができるか提案していただけますか？たとえば、10 ^ 100と言う非常に大きな整数があり、それが200と言う別の整数で割り切れるかどうかを確認したい場合、10 ^ 100が2と5で割り切れるかどうかを試しました（最後の桁に注意してください）。Aが十分に小さい場合は、A％B == 0であるかどうかを直接確認できますが、これをより大きな数で試していました。ありがとう、

Answer 1

の因数分解で素数が現れる回数を数え、B少なくともの因数分解で素数が現れることを確認する必要がありAます。

したがって、200 = 2 ^{3 *} 52 。次に、23と52で割り切れる場合に限り、200^で割り切れ^ます。A

因数分解をすでに何とか知っていない限り、因数分解Aは単にそれをで割るよりもはるかに遅いですB。その理由は、を完全に因数分解するのに多くの試行除算（または同等の作業）が必要Aであるのに対し、による除算性をチェックするのに1つの試行除算しか必要としないためBです。結局のところ、Bが素因数である場合を考えてみてください。必要なのはそれらの1つであるかどうかをテストすることだけだったときに、のすべての素因数を見つけました。これはおそらく作業が少なくなることはありません。AB

Answer 2

これは素因数分解についての最良のアイデアです。ここに書かれているのは、より多くの人々に知らせて参加させることです。

素因数分解の新しい方法1+2 + 3 +4+……+k= Ny、（k

真の金は火を恐れます、あなたはテストすることができます1+2+3+...+k=Ny(k<N/2)。

「k」と「y」はどうすればわかりますか？

「P」は「N」の因数ですGCD(k,N)=P。

このアイデアは、フェルマーの素因数分解よりも簡単な方法かもしれませんmethod(x^2-N=y^2)。

真の金は火を恐れます、あなたはテストすることができます1+2+3+...+k=Ny(k<N/2)。

私のG+とBLOGのプロセスの詳細。