鉴于其主要分解,生成数量的所有因素
-
01-10-2019 - |
题
如果您已经有一个数字的主要分解,那么获得该数字的所有因素的最简单方法是什么?我知道我可以从2循环到SQRT(n)并找到所有可分配的数字,但这似乎效率低下,因为我们已经有了主要分解。
我想这基本上是组合 /选择功能的修改版本,但是我似乎发现的只是计算组合数量的方法,以及计算因子数量的方法,而不是实际生成组合 /因素。
解决方案
想象一下,主要的除数是桶中的球。例如,如果您的数字的主要除数为2、2、2、3和7,那么您可以将“ Ball 2”的0、1、2或3个实例进行。同样,您可以服用“ 3'0或1次球”,而“球7” 0或1次。
现在,如果您将“ 2'2”和“球7”进行一次,那么您会得到除数2*2*7 = 28。 *2*2*3*7等于数字本身。
最后,为了获得可以从水桶中取出的所有可能的球组合,您可以轻松使用递归。
void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
if (currentDivisor == primeDivisors.length) {
// no more balls
System.out.println(currentResult);
return;
}
// how many times will we take current divisor?
// we have to try all options
for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
currentResult *= primeDivisors[currentDivisor];
}
}
现在您可以在上面的示例上运行它:
findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);
其他提示
Dimo414,生成因子通常被认为是非常困难的任务。实际上,保护您的大多数重要资产(即金钱,信息等),基于简单但非常困难的考虑数字的任务。请参阅有关RSA加密方案的本文 http://en.wikipedia.org/wiki/rsa_(Cryptosystem). 。我离题。
为了回答您的问题,正如Nikita所指出的那样,组合方法是您的最佳方法(BTW,您的解释中的荣誉)。
我知道我可以从2循环到SQRT(n)并找到所有可分配的数字
由于与生成素数相关的非常相似的概念,许多人就得出了这个结论。不幸的是,这是不正确的,因为您会错过比SQRT(N)大的几个因素(我会让您向自己证明这一点)。
现在,为了确定任何给定数字n的因素数量,我们研究了 n. 。如果 n = p一种, ,那么我们知道n将有(A + 1)因素(1,p,p2, ,...,P一种)。这是确定因素总数的关键。如果 n 有多个主要因素,说
n = p1一种· p2b··· pkr
然后使用 产品规则 计数(http://en.wikipedia.org/wiki/rule_of_product),我们知道会有
m = (A + 1)·(B + 1)···(R + 1)
因素。现在,我们要做的就是找到通过主要分解给我们的数字的所有可能组合。下面是R中的一些代码,希望能够演示我所解释的内容。
我的代码的第一部分对原始性进行了简单的检查,因为如果数字是素数,则唯一的因素是1和本身。接下来,如果这个数字不是素数且大于1,我首先找到了数字的主要分解,例如我们有,
n = p1一种· p2b··· pkr
然后,我只发现独特的素数躺着 单次, 因此,在此示例中,uniprimes将包含(p1, ,p2, ,pk)。然后,我找到每个素数的所有功能,然后将其添加到累积的数组中 myfactors。 制作此阵列后,我发现myFactor中元素的所有可能产品组合。最后,我在数组中添加1个(因为这是一个微不足道的因素),然后对其进行排序。瞧!它非常快,可以适用于很多因素。
我试图使代码尽可能翻译成其他语言(即,我认为您已经构建了一个生成质量分解(或使用内置功能)和质数测试功能的函数。)而且我没有' t使用。干杯!
factor2 <- function(MyN) {
CheckPrime <- isPrime(MyN)
if (CheckPrime == F && !(MyN == 1)) {
MyPrimes <- primeFactors(MyN)
MyFactors <- vector()
MyPowers <- vector()
UniPrimes <- unique(MyPrimes)
for (i in 1:length(UniPrimes)) {
TempSize <- length(which(MyPrimes == UniPrimes[i]))
for (j in 1:TempSize) {
temp <- UniPrimes[i]^j
MyPowers <- c(MyPowers, temp)
}
}
MyFactors <- c(MyFactors, MyPowers)
MyTemp <- MyPowers
MyTemp2 <- vector()
r <- 2
while (r <= length(UniPrimes)) {
i <- 1L
while (i <= length(MyTemp)) {
a <- which(MyPrimes > max(primeFactors(MyTemp[i])))
for (j in a) {
temp <- MyTemp[i]*MyPowers[j]
MyFactors <- c(MyFactors, temp)
MyTemp2 <- c(MyTemp2, temp)
}
i <- i + 1
}
MyTemp <- MyTemp2
MyTemp2 <- vector()
r <- r + 1
}
} else {
if (MyN == 1) {
MyFactors <- vector()
} else {
MyFactors <- MyN
}
}
MyFactors <- c(1, MyFactors)
sort(MyFactors)
}