0

here is sample code 

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;

        }

Note : I have initialize factors as global.

Above code will work fine for sample inputs 90 , 18991325453139 but will not work for input 12745267386521023 ... so how can I do that ? How can I achieve this efficiently ... I know recursive call will consume memory that's why I have checked the last input using without recursion .. But its not working too

4

3 回答 3

3

你可以使用它，如果

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;
    }
}
于 2011-07-31T12:36:26.800 回答
3 
using System.Collections;  

      public static int[] PrimeFactors(int num)  
       {  
           ArrayList factors = new ArrayList();  

           bool alreadyCounted = false;  
           while (num % 2 == 0)  
           {  
               if (alreadyCounted == false)  
               {  
                   factors.Add(2);  
                   alreadyCounted = true;  
               }  
               num = num / 2;  
           }  

           int divisor = 3;  
           alreadyCounted = false;  
           while (divisor <= num)  
           {  
               if (num % divisor == 0)  
               {  
                   if (alreadyCounted == false)  
                   {  
                       factors.Add(divisor);  
                       alreadyCounted = true;  
                   }  
                   num = num / divisor;  
               }  
               else  
               {  
                   alreadyCounted = false;  
                   divisor += 2;  
               }  
           }  

           int[] returnFactors = (int[])factors.ToArray(typeof(int));  

           return returnFactors;  
       }

我刚刚从Smokey Cogs复制并发布了一些代码，因为这是一个非常常见的问题。

该代码比您的代码做得更好。

首先你除以二，直到数字不再是偶数。从那里，您可以从 3 开始并增加 2（跳过每个偶数），因为所有 2 都已被分解。

尽管如此，还是有改进的方法。想想代码中“alreadyCounted”的用法。它是绝对必要的吗？例如，使用

    if (num % 2 == 0)
{
        factors.Add(2);
        num = num/2;
}

    while( num %2 == 0)
        {num = num/2;}

允许您在开始时跳过额外的比较。

RiaD 还给出了一个很好的启发式方法，factor^2 > num暗示 num 是素数。这是因为, 所以除以(sqrt(n))^2 = n之后的唯一数字就是它自己，一旦你取出了之前的素数。sqrt(n)numnum

希望能帮助到你！

于 2011-07-31T12:54:34.500 回答
1

要查看如何在 C# 中查找给定数字的因数，请参阅此（重复？） StackOverflow 问题。

您的代码有几点：

  • 如果使用天真的搜索，则不需要递归，只需在方法中构建一个因子列表并在最后（或使用yield）返回它。
  • 您的第二个 if 语句是多余的，因为它包装了具有相同条件的 while 循环。
  • 您应该使用整数类型（并且无符号整数类型将允许比其有符号对应物更大的数字，例如uintor ulong），而不是decimal使用整数。对于任意大的整数，使用System.Numerics.BigInteger.
  • 如果您逐步向上搜索一个因子，当您到达原始数字的平方根时，您可以停止查找，因为没有任何因子可以大于那个。

另外，请注意，没有已知的有效算法可用于分解大数（有关简要概述，请参见Wikipedia ）。

这是基于上述观察的示例代码：

static IList<BigInteger> GetFactors(BigInteger n)
{
    List<BigInteger> factors = new List<BigInteger>();
    BigInteger x = 2;
    while (x <= n)
    {
        if (n % x == 0)
        {
            factors.Add(x);
            n = n / x;
        }
        else
        {
            x++;
            if (x * x >= n)
            {
                factors.Add(n);
                break;
            }
        }
    }
    return factors;
}

请注意，这仍然是一个相当幼稚的算法，可以很容易地进一步改进。

于 2011-07-31T12:57:03.740 回答