c# - 分解最大数

Question

这里是示例代码

public static decimal factorization(decimal num, decimal factor)
        {

            if (num == 1)
            {
                return 1;
            }
            if ((num % factor)!= 0)
            {

                while(num% factor != 0)
                {
                    factor++;
                }

            }

            factors.Add(factorization(num / factor, factor));
            return factor;

        }

注意:我将初始化因子设置为全局。

以上代码适用于示例输入 90、18991325453139 但不适用于输入 12745267386521023 ... 那么我该怎么做呢？我怎样才能有效地实现这一目标......我知道递归调用会消耗内存，这就是为什么我检查了最后一个输入而没有递归......但它也不起作用

Answer 1

你可以使用它，如果

factor*factor > num

那么num是质数

它将复杂度从 O(n) 降低到 O(sqrt(n))

编辑

while(num% factor != 0)
{
    factor++;
    if(factor*factor>num){ // You can precalc sqrt(num) if use big arifmetic
        factor=num; //skip factors between sqrt(num) and num;
    }
}