素因式分解

Question

我正在做一个Objective项目，我需要做一些素因式分解，所以我想出了以下算法，即99% C，除了数组部分-C中最容易实现，因为它动态地为元素分配新的内存，因为它们只是简单的添加。目标-C部分是相当清楚的。

我主要是寻找反馈的算法，不一定是编码风格和诸如此类，但我会很高兴的反馈，我可以改进的东西！在我使用O3优化的机器上，分解1234567890的时间不到2秒。我真的不知道这是好是坏。我想在它中添加一个用于先前计算的因式分解的表，当在大的数字上，您很可能会遇到不止一次的数字(例如，4、6等)。我可能会添加一个函数，如果是偶数，在这些因素中添加一个2，而不做可能提高性能的除法/素数检查。

//Declare an array
NSMutableArray *factors;

bool isPrime(long n) {

    //Check if even or ends in a five
    if ((n % 2 == 0 && n > 2) || (n > 5 && n % 10 == 5)) {
        return 0;
    }

    if (n == 2) return 1;

    //set upper bound to square root
    long u = sqrt(n);
    long c = 0;

    for (long i = 3; i <= u; i+=2)
        if (n % i == 0) {
            c++;
            break;
        }

    return !c;
}


void factorize(long n) {

    //If prime return
    if (isPrime(n)) {
        [factors addObject:@(n)];
        return;
    }

    for (long i = n/2; i > 1; i--) {
        if (n % i) continue; //Check if indivisible

        long d = n/i;

        bool iP = isPrime(i), dP = isPrime(d);

        if (iP)
            [factors addObject:@(i)];
        else
            factorize(i);

        if (dP)
            [factors addObject:@(d)];
        else
            factorize(d);

        return;
    }
}

int main(int argc, const char * argv[]) {

    factors = [NSMutableArray array];

    long n = 1234567890;
    factorize(n);

    NSLog(@"%@", factors);

    return 0;
}

Answer 1

您的算法首先尝试找出最大的因素。这是无效的，因为您必须测试每个可能的因素，无论它是否是素数。

从最小的因素开始要有效得多。如果以这种方式将数字除以每个因素，那么您将只得到素因子，而素测试函数isPrime()就过时了。从除以2开始，然后按递增顺序测试可能的奇数因素。(如果您有一个预先计算的素数列表，那么这一点可以进一步改进。)

在我的计算机上，这将分解1234567890的运行时从1.6秒减少到0.00005秒。

此外，对于此更改，不再需要全局factors变量，您的方法可以如下所示：

NSMutableArray * primeFactorization(long n) {

    NSMutableArray *factors = [NSMutableArray array];

    // Divide by 2:
    while (n > 1 && n % 2 == 0) {
        [factors addObject:@(2)];
        n /= 2;
    }

    // Divide by 3, 5, 7, ...
    //
    // i is a possible *smallest* factor of the (remaining) number n.
    // If i * i > n then n is either 1 or a prime number.
    for (long i = 3; i * i <= n; i += 2) {
        while (n > 1 && n % i == 0) {
            [factors addObject:@(i)];
            n /= i;
        }
    }

    if (n > 1) {
        // Append last prime factor:
        [factors addObject:@(n)];
    }

    return factors;
}

int main(int argc, const char * argv[]) {

    long n = 1234567890;

    NSDate *startTime = [NSDate date];
    NSArray *factors = primeFactorization(n);
    NSLog(@"time: %f", -[startTime timeIntervalSinceNow]);

    NSLog(@"%@", factors);

    return 0;
}

Answer 2

对算法的反馈

//Check if even or ends in a five
if ((n % 2 == 0 && n > 2) || (n > 5 && n % 10 == 5)) {
    return 0;
}

检查您的数字是否除以5的部分进行了很少的优化，因为它是在下面的循环的第二次迭代中检查的。

for (long i = 3; i <= u; i+=2)
    if (n % i == 0) {
        c++;
        break;
    }

我建议为所有素数创建一个缓存，例如100000，然后像这样重写循环：

for (long i = 0; i < primeCacheSize; i++)
    if (n % primeCache[i] == 0) {
        return 1;
    }
for (long i = 100001; i <= u; i++)
    if (n % i == 0) {
        return 1;
    }
return 0;

这有点奇怪：

//If prime return
if (isPrime(n)) {
    [factors addObject:@(n)];
    return;
}

for (long i = n/2; i > 1; i--) {
    if (n % i) continue; //Check if indivisible

该代码将如何在208907 * 208907 * 208907 (9117147423118643)上工作？函数isPrime将确定n除以208907，返回false，然后开始从9117147423118643 / 2向下迭代。看起来像是一个无限循环(也是无用的)。

我可能建议的解决方案是:如果n是素数，则让isPrime函数返回数字本身，如果不是，则返回数字除数。

for (long i = 0; i < primeCacheSize; i++)
    if (n % primeCache[i] == 0) {
        return primeCache[i];
    }
for (long i = 100001; i <= u; i++)
    if (n % i == 0) {
        return i;
    }
return n;

并像这样重写分解：

void factorize(long n) {

//If prime return
while (n > 1) {
    divider = isPrime(n);
    [factors addObject:@(divider)];
    n /= divider;
}

Answer 3

考虑到这个答案是用C标记标记的，并且用户非常恰当地指出代码是99%的C，我认为可能值得演示这个问题的C解决方案是多么简单。

目标C的两个方面是用户使用的。

1. NSMutableArray。这很方便，它为我们处理数组的大小调整。但是，需要注意的是，NSMutableArray的大小并没有什么神奇之处。目标-C可变数组的大小与C数组的大小相同.
2. NSNumber。我们实际上并没有直接看到NSNumber，但这正是@()语法所做的--创建NSNumber对象。为什么？因为NSArray不能存储原始数据类型。它必须存储指针。

除非实际意图是在其他目标C代码中使用这个数组，因为在这些代码中，NSNumber对象实际上更容易处理，否则在这里使用objects并没有特别好的理由，除非在使用C样式数组时可能会感到不舒服。

所以，这是我在C中解决这个问题的方法。

作为起点，我使用了马丁R的回答，这实际上也非常类似于我用于这里一个稍微不同的问题的算法。

请注意，下面的代码片段包括马丁答案中的代码，这样两个解决方案可以并排比较，以防他编辑/删除他的答案。

马丁的回答很好：

NSMutableArray * primeFactorization(long n) {

    NSMutableArray *factors = [NSMutableArray array];

    // Divide by 2:
    while (n > 1 && n % 2 == 0) {
        [factors addObject:@(2)];
        n /= 2;
    }

    // Divide by 3, 5, 7, ...
    //
    // i is a possible *smallest* factor of the (remaining) number n.
    // If i * i > n then n is either 1 or a prime number.
    for (long i = 3; i * i <= n; i += 2) {
        while (n > 1 && n % i == 0) {
            [factors addObject:@(i)];
            n /= i;
        }
    }

    if (n > 1) {
        // Append last prime factor:
        [factors addObject:@(n)];
    }

    return factors;
}

我用直C的方法：

long * cPrimeFactorization(long n, long *factorCount) {
    long currentSize = 2;
    long currentIndex = 0;
    long *factors = malloc(sizeof(long) * currentSize);

    while (n > 1 && n % 2 == 0) {
        factors[currentIndex++] = 2;
        if (currentIndex >= currentSize) {
            currentSize *= 2;
            long *reallocFactors = realloc(factors, currentSize * sizeof(long));
            if (reallocFactors) {
                factors = reallocFactors;
            } else {
                printf("realloc failed");
                free(factors);
                return NULL;
            }
        }
        n /= 2;
    }

    for (long i = 3; i * i <= n; i += 2) {
        while (n > 1 && n % i == 0) {
            factors[currentIndex++] = i;
            if (currentIndex >= currentSize) {
                currentSize *= 2;
                long *reallocFactors = realloc(factors, currentSize * sizeof(long));
                if (reallocFactors) {
                    factors = reallocFactors;
                } else {
                    printf("realloc failed");
                    free(factors);
                    return NULL;
                }
            }
            n /= i;
        }
    }

    if (n > 1) {
        factors[currentIndex++] = n;
    }
    *factorCount = currentIndex; 
    return factors;
}

并排运行：

int main(int argc, const char * argv[]) {
    long n = 1234567890;

    NSDate *startTime = [NSDate date];
    NSArray *oFactors = primeFactorization(n);
    NSLog(@"time (Objective-C): %f", -[startTime timeIntervalSinceNow]);

    startTime = [NSDate date];
    long factorCount;
    long * cFactors = cPrimeFactorization(n, &factorCount);
    NSLog(@"time (C): %f", -[startTime timeIntervalSinceNow]);

    NSLog(@"%@", oFactors);
    for (long i = 0; i < factorCount; ++i) {
        printf("%li\n", cFactors[i]);
    }

    return 0;
}

为了保持基准测试的一致性，我只使用了Objective方法(因为Martin已经有了它，而且我不想使用C方法)。我尝试了几个不同的数字，并运行了他们所有的多次。C方法在每种情况下都运行得更快。

与速度相比，C方法实际上比目标C方法占用更少的内存.目标-C数组不仅比C数组具有更多的开销(每个索引大小相同，8字节)，而且目标-C数组是指向对象的指针的索引。因此，objects数组已经比C数组稍大一些，另外还有一些更大的内存空间，可以将所有NSNumber对象都保存在堆中。

我们必须花费大量的时间在堆栈上创建这些NSNumber对象，这是目标C解决方案速度慢的原因之一。它也比较慢，因为将消息传递到对象(我们多次调用的addObject: )要比在内存位置直接插入一个值(这就是我们对C数组所做的)要慢得多。

请注意，我绝对是一个目标-C程序员，我不是一个最轻微的C程序员。我的C代码几乎肯定还有改进的余地。但是作为目标C程序员，我们必须始终记住纯C应该永远是一种选择。

值得注意的是，这种速度(和内存)的差异在非常大的二次幂下变得特别明显。例如，使用2^49，即562,949,953,421,312，目标-C解决方案在我的计算机上花费了几乎3倍的时间。