25

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

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

4

2 回答 2

34

想象素数除数是桶里的球。例如，如果您的数字的主要因数是 2、2、2、3 和 7，那么您可以取 0、1、2 或 3 个“球 2”的实例。类似地，您可以取 'ball 3' 0 或 1 次和 'ball 7' 0 或 1 次。

现在，如果你拿'ball 2'两次和'ball 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);
于 2010-09-05T03:30:59.237 回答
6

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

为了回答您的问题，如 Nikita 所指出的那样，组合方法是您最好的方法（顺便说一句，对您的解释表示赞赏）。

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

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

现在，要确定任何给定数 n 的因子数，我们查看 n 的素数分解。如果n = p a，那么我们知道 n 将有 ( a + 1 ) 个因数 ( 1, p, p 2 , ... , p a )。这是确定因子总数的关键。如果n有多个素因数，比如说

n = p 1 a · p 2 b ··· p k r

然后使用计数的产品规则（http://en.wikipedia.org/wiki/Rule_of_product），我们知道会有

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

因素。现在，我们需要做的就是找到素数分解给我们的所有可能的数字组合。下面是 R 中的一些代码，希望能展示我所解释的内容。

我的代码的第一部分对素数进行了简单的检查，因为如果数字是素数，则唯一的因数是 1 和它本身。接下来，如果数字不是素数且大于 1，我首先找到数字的素数分解，假设我们有，

n = p 1 a · p 2 b ··· p k r

然后我只找到标记为 UniPrimes 的唯一素数，因此对于这个例子，UniPrimes 将包含 ( p 1 , p 2 , p k )。然后我找到每个素数的所有幂并将其添加到标记为 MyFactors 的数组中。制作完这个数组后，我会在 MyFactors 中找到所有可能的元素产品组合。最后，我将 1 添加到数组中（因为它是一个微不足道的因素），然后对其进行排序。瞧！它非常快，适用于具有许多因素的非常大的数字。

我试图使代码尽可能地翻译成其他语言（即我假设您已经构建了一个生成素数分解（或使用内置函数）和素数测试函数的函数。）我没有t 使用 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)
}
于 2015-01-29T14:39:14.140 回答