在给出其素数因子分解的情况下生成数字的所有因子

Question

如果您已经对数字进行了素数分解,那么获得该数字的所有因子的最简单方法是什么？我知道我可以从2循环到sqrt(n)并找到所有可分的数字,但这似乎效率低,因为我们已经有了素数分解.

我想它基本上是组合/选择功能的修改版本,但我似乎找到的只是计算组合数量的方法,以及计算因子数量的方法,而不是实际生成组合/因子.

Answer 1

想象一下,主要的除数是一个桶中的球.例如,如果您的数字的主要除数是2,2,2,3和7,那么您可以采用0,1,2或3个"球2"实例.同样,你可以把'球3'0或1次和'球7'0或1次.

现在,如果你把'球2'两次和'球7'一次,你得到除数2*2*7 = 28.同样,如果你没有球,你得到除数1,如果你拿走所有球,你得到除数2*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);

Answer 2

dimo414,生成因子通常被认为是一项非常困难的任务.事实上,保护您的大部分重要资产(即金钱,信息等),都依赖于简单但极其困难的数字因素.请参阅有关RSA加密方案的文章http://en.wikipedia.org/wiki/RSA_(cryptosystem).我离题了.

为了回答你的问题,组合方法是你最好的方法,正如尼基塔所指出的那样(顺便说一下,你的解释就是赞誉).

我知道我可以从2循环到sqrt(n)并找到所有可分的数字

由于与生成素数相关的非常相似的概念,许多人跳到这个结论.不幸的是,这是不正确的,因为你会错过几个不是素数的sqrt(n)因子(我会让你自己证明这一点).

现在,以确定的因素,对于任何给定数量的数n,我们期待的因式分解ñ.如果n = p ^a,那么我们知道n将具有(a + 1)个因子(1,p,p ²,...,p ^a).这是确定因素总数的关键.如果n有多个素因子,比如说

N = P ₁ ^一· p ₂ ^b ... p _ķ ^ř

然后使用计数产品规则(http://en.wikipedia.org/wiki/Rule_of_product),我们知道会有

m =(a + 1)·(b + 1)···(r + 1)

因素.现在,我们需要做的就是通过素数因子分解找到给我们的数字的每种可能组合.下面是R中的一些代码,希望能够证明我所解释的内容.

我的代码的第一部分简单检查了素数,因为如果数字是素数,那么唯一的因素是1和它自己.接下来,如果数字不是素数且大于1,我首先找到数字的素数因子化,比如我们有,

N = P ₁ ^一· p ₂ ^b ... p _ķ ^ř

然后我发现只有UniPrimes标记的唯一素数,因此对于这个例子,UniPrimes将包含(p ₁,p ₂,p _k).然后我找到每个素数的所有幂并将其添加到一个标记为MyFactors的数组中.在创建此数组之后,我会在MyFactors中找到元素的每个可能的产品组合.最后,我向数组添加1(因为它是一个微不足道的因素),并对其进行排序.瞧!它非常快,适用于具有许多因素的非常大的数字.

我试图使代码尽可能地翻译成其他语言(即我假设你已经构建了一个生成素数分解(或使用内置函数)和素数测试函数的函数.)我没有'使用R独有的专用内置函数.如果不清楚,请告诉我.干杯!

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)
}