分解大于100位的整数 [英] Decompose integers larger than 100 digits
问题描述
X和Y是大于100个数字的整数.找到整数P，该整数在[X，Y []范围内，并且可以保证最佳"素数分解(即具有最多唯一素数因子的分解).
我所做的只是检查素数并分解范围内的每个数字，然后找到遵守规则的数字.还有其他方法吗?
按顺序(2,3,5,7 ...)列出所有素数的列表，然后开始将它们相乘(2 * 3 * 5 * .. .)，直到得到一个数字> =X.将此数字称为P'.如果它的< = Y，则完成，P = P'.如果不是，则开始计算P'/2，P'/3，P'/5等，以寻找数字[X，Y].如果找不到，并得到一个<数字； X，尝试乘以P'，然后再加下一个质数，然后继续.如果仍然失败，则范围[X，Y]很小，因此请退回考虑将该范围内所有数字分解的方法.
对于较小范围(YX小)，分配大小为Y-X + 1的数组，将其归零，然后对于所有质数< = YX，将一个加到对应于质数倍数的数组元素上(简单) seive).然后搜索总数最大的元素.如果那个总数n等于(Y-X) n > = X，那么答案就是这个.如果不是，请继续筛选比Y-X大的素数，直到达到某个素数p，使得表中的n对应p n > X ...
以上两种方法之一应该起作用，具体取决于范围的大小...
X and Y are integers larger than 100 digits. Find the integer P which is within the range [X, Y[ and that guaranties the "best" prime decomposition (i.e. the decomposition with the most unique prime factors).
What I've done is just check the primality and decompose each number in the range and find the number that respects the rule. Is there any other way to do this?
Edit:
In the above example, 123456 is decomposed to
2^6 * 3^1 * 643^1, that's 2 * 2 * 2 * 2 * 2 * 2 * 3 * 643 but only 3 unique factors.
While the answer, 123690, is decomposed to 6 unique factors
2^1 * 3^1 * 5^1 * 7^1 * 19^1 * 31^1.
Take the list of all primes in order (2,3,5,7...) and start multiplying them (2 * 3 * 5 *...) until you get a number >= X. Call this number P'. If its <= Y, you're done, P = P'. If not, start computing P'/2, P'/3, P'/5 etc looking for a number [X,Y]. If you don't find it and get to a number < X, try multiplying in then next prime to P' and continuing. If this still fails, then the range [X,Y] is pretty small, so fall back to the method of factoring all the numbers in that range.
For a small range (Y-X is small), allocate an array of size Y-X+1, zero it, then for all primes <= Y-X, add one to the array elements corresponding to multiples of the prime (simple seive). Then search for the element with the largest total. If that total n is such that (Y-X)n >= X, then that is the answer. If not, continue sieving primes larger than Y-X until you get to some prime p such that pn > X for some n in the table...
One of the two above methods should work, depending on how large the range is...
这篇关于分解大于100位的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
