algorithm - 通过素数分解检查整除性

Question

为了检查一个整数（比如 A）被另一个整数（比如 B）整除，我尝试了一种方法，即分解 B 并检查 A 是否可以被 B 的所有素因子整除。但是我不确定它是否正确？你能建议可以做什么吗？例如，如果我们有一个非常大的整数，比如 10^100，并且我们想检查它是否可以被另一个整数整除，比如 200，那么我正在尝试 10^100 是否可以被 2 和 5 整除（通过注意最后一位数字）。如果 A 足够小，我们可以直接检查 A%B==0 但我正在尝试更大的数字。谢谢，

Answer 1

您必须计算素数在 的因式分解中出现的次数B，并确保它在 的因式分解中至少出现同样多次A。

所以，200 = 2 ³ * 5 ²。ThenA能被 200 整除当且仅当它可以被 2 ³和 5 ²整除。

除非您已经以某种方式知道因式分解，否则因式分解A远比仅除以B. 原因是需要许多试除法（或等效工作）才能完全分解A，而只需要一个试除法来检查它是否可被 整除B。毕竟，考虑B素数的情况：您已经找到的所有素因数A，而您所需要的只是测试是否B是其中之一。这不可能是更少的工作。

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 中详细了解该过程。