给定素数分解生成数的所有因子

假设素数因子是桶里的球。例如,如果你的数的素数因子是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);

生成因子通常被认为是一项非常困难的任务。事实上,保护你的大部分重要资产(如金钱、信息等)取决于简单但极其困难的数字分解任务。请参阅这篇关于RSA加密方案的文章 http://en.wikipedia.org/wiki/RSA_(cryptosystem)

为了回答你的问题,组合方法是你最好的方法,正如Nikita所指出的(顺便说一句,很感谢你的解释)。

我知道我可以从2循环到sqrt(n),然后找到所有可整除的

现在,为了确定任意给定数n的因子个数,我们研究了n的素因子分解 n=p ^一 ,那么我们就知道n( a+1级 )因素( 1,p,p , ... ,第 ). 这是决定因素总数的关键。如果 比如说,有多种主要因素

^一 · ^b p ^r

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

米 ) · b+1级 ) ··· ( 无线电+1 )

我的代码的第一部分做了一个简单的素数检查,因为如果数字是素数,唯一的因子是1和它本身。下一步,如果这个数不是素数并且大于1,我首先找到这个数的素数因子分解,假设我们有,

n=p ^一 · p ₂ ··· _k

然后我只找到唯一的素数 在这个例子中,单素数包含( p _{1 2} ,第 我的因素。

我试图使代码尽可能地可翻译到其他语言(即,我假设您已经构建了一个生成素数分解(或使用内置函数)和素数测试函数的函数)并且我没有使用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)
}