难.我首先开始检查小素数(在你的例子中:4,7,8.产品有2 ^ 5的因子.你除以2的幂,留下1,7,1.然后你做同样的3 ,5,7等等到X).
现在你需要找到一个更大的素数p> X,它比你找到的最高值更高.花费大量时间来找到仅发生一次的主要因素似乎是浪费.您需要具有多个数字因子的素数.计算每对数字的gcd并查看这些数字的素数因子.有很多细节需要解决,这就是我开始"困难"的原因.
最坏的情况是你不能轻易找到任何两次出现的素数,所以你需要检查每个数字是否包含素数的平方因子.
例如:您检查了多达1000的因子,并且您发现素数的最高功率为83 ^ 3.所以现在你需要找到一个更大的素数,这是第四种力量或显示没有.计算成对gcd(最大公约数).一个大素数可以是来自四个不同数字的这些gcd的倍数的除数,或者p可以是三个gcd的因子,p ^ 2是一个数的因子等.
澄清原则:假设你有两个巨大的数字x和y,你想知道哪个是分割xy的素数的最高幂.你可以将x和y因子分解并从那里开始.如果它们都是素数或两个大素数的乘积,比如x = p或pq,y = r或rs,这需要很长时间.
现在计算x和y的gcd.如果最大公约数是z> 1,则z是x和y的因子,因此z ^ 2是xy的因子.如果最大公约数是1,那么x和y没有共同因子.由于我们不需要不是正方形的因子,我们寻找正方形和更高的因子.为此,您只需要将因子除以x ^(1/3)或y ^(1/3).