0

これがサンプルコードです

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では機能しません...では、どうすればよいですか？どうすればこれを効率的に達成できますか...再帰呼び出しはメモリを消費することがわかっているので、再帰なしで最後の入力をチェックしました..しかしそれも機能していません

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;  
       }

これは非常に一般的な問題であるため、SmokeyCogsからコードをコピーして投稿しました。

このコードは、あなたのコードよりも優れた機能をいくつか備えています。

まず、数が均等でなくなるまで2で割ります。そこから、3から始めて、2ずつ増やす（偶数ごとにスキップする）ことができます。これは、2がすべて因数分解されているためです。

それにもかかわらず、改善する方法があります。コードでの「alreadyCounted」の使用法について考えてみてください。それは絶対に不可欠ですか？たとえば、

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

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

最初に余分な比較をスキップできます。

RiaDは、factor^2 > numnumが素数であることを意味する優れたヒューリスティックも提供しました。これは、前の素数を取り除いた後の除算(sqrt(n))^2 = nの数はそれ自体だけになるためです。sqrt(n)numnum

それが役に立てば幸い！

于 2011-07-31T12:54:34.500 に答える
1

C＃で特定の数値の因子を見つける方法を確認するには、この（重複？）StackOverflowの質問を参照してください。

コードに関するいくつかのポイント：

  • 単純な検索を使用する場合は再帰の必要はありません。メソッド内の要素のリストを作成し、最後にそれを返す（またはを使用するyield）だけです。
  • 2番目のifステートメントは、同じ条件でwhileループをラップするため、冗長です。
  • 整数を使用する場合ではなく、整数型を使用する必要があります（符号なし整数型では、符号付きの対応する整数型よりも大きな数値が許可されます（例：uintまたはulong））decimal。任意に大きい整数の場合は、を使用しますSystem.Numerics.BigInteger。
  • 因子を上向きに段階的に検索する場合、元の数の平方根まで到達したときに、それより大きくなる因子はないため、検索を停止できます。

また、多数を因数分解するための既知の効率的なアルゴリズムがないことに注意してください（簡単な概要についてはウィキペディアを参照してください）。

上記の観察に基づいたサンプルコードは次のとおりです。

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 に答える