Project Euler Question 3ヘルプ

StackOverflow https://stackoverflow.com/questions/201374

質問

Project Eulerで作業しようとしており、問題03の障壁にぶつかっています。小さい数値で動作するアルゴリズムを持っていますが、問題3では非常に大きな数値を使用しています。

問題03： 13195の素因数は5、7、13、および29です。 数600851475143の最大の素因数は何ですか？

C＃での私のソリューションは次のとおりです。1時間近く実行されていると思います。私は実際に自分でこれを解決したいので、答えを探していません。主にいくつかの助けを探しています。

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }
役に立ちましたか？

解決

最初に、n / 2で検索を開始する代わりに、nの平方根で検索を開始します。半分の要素を取得し、残りの半分はそれらを補完します。

eg：

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

他のヒント

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

これは十分に速いはずです...注意してください、プライムをチェックする必要はありません...

実際、この場合、素数性をチェックする必要はなく、見つけた要素を削除するだけです。 n == 2から始めて、上方にスキャンします。 evil-big-number％n == 0の場合、evil-big-numberをnで除算し、smaller-evil-numberに進みます。 n <！> gt; = sqrt（big-evil-number）のときに停止します。

最新のマシンでは数秒以上かかりません。

質問は最大素因数を求めますが、必ずしも最初にそれを見つけなければならないというわけではありません...

実行しているチェックの量を減らす必要があります...テストする必要がある数字を考えてください。

より良いアプローチについては、 Erathosthenesのふるいをご覧ください...あなたは正しい方向を指した。

nicfの回答を受け入れた理由：

オイラーでの問題は問題ありませんが、一般的な場合、これは効率的な解決策にはなりません。なぜ因子に偶数を試してみますか？

  • nが偶数の場合、左にシフトします（除算 2）もうなくなるまで。もしそれが 1、2が最大の素数 要因。
  • nが偶数でない場合、する必要はありません 偶数をテストします。
  • 停止できるのは本当です sqrt（n）。
  • 素数をテストする必要があるのは 要因。テストする方が速いかもしれません kがnを除算してからテストするかどうか しかし、素数のため。
  • 上限を最適化できます 要因を見つけたときのハエ。

これにより、次のようなコードが生成されます。

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

すべての因子2および3が削除された場合、nを6で割ることはできないため、いくつかの剰余検定があります。 iには素数のみを許可できます。

例として、21の結果を見てみましょう：

21は偶数ではないため、上限sqrt（21）（〜4.6）でforループに入ります。 その後、21を3で割ることができるため、結果= 3およびn = 21/3 = 7になります。ここで、sqrt（7）までテストするだけです。 3よりも小さいので、forループは完了です。 nの最大値と結果、n = 7を返します。

私がやった方法は、エラトステネスのふるいを使用して2から始まる素数（p）を検索することでした。このアルゴリズムは、まともな高速マシンで<！> lt; 2sで1000万未満のすべての素数を見つけることができます。

見つかったすべての素数に対して、整数除算ができなくなるまで、テスト対象の数に除算します。 （つまり、n % p == 0を確認し、trueの場合は分割します。）

一度n = 1で、完了です。正常に分割されたnの最後の値が答えです。傍注では、途中で2 <= n <= sqrt(p)のすべての素因数も見つけました。

PS：前述したように、<=>の間の素数のみを検索する必要があります。これにより、Sieve of Eratosthenesは非常に高速で簡単に実装できるアルゴリズムになります。

答えが見つかったら、ブラウザに次のように入力します;）

http://www.wolframalpha.com/input/?i= FactorInteger（600851475143）

Wofram Alphaはあなたの友達です

Javaでの再帰アルゴリズムの使用は1秒未満で実行されます... <！> quot; brute-forcing <！> quot;除去できます。また、中間計算によってソリューションスペースがどのように削減されるかを確認します。

C ++の簡単操作：

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

C ++でのこのソリューションは、Intel Quad Core i5 iMac（3.1 GHz）で3.7ミリ秒かかりました

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

すべてのProject Eulerの問題は1分もかからないはずです。 Pythonでの最適化されていない再帰的な実装でさえ、1秒未満です[0.09秒（cpu 4.3GHz）]。

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

これを見たいかもしれません：

そしてlill mudのソリューションが好きです：

  

require <！> quot; mathn.rb <！> quot;
  puts 600851475143.prime_division.last.first

確認しましたこちら

不正行為と見なされるかもしれませんが、haskellでの1つの可能性は、書くことです（レコードについては、自分で行を書き、eulerprojectスレッドをチェックしていません）。 

import Data.Numbers.Primes
last (primeFactors 600851475143)

Miller-Rabin Primality Test を使用して、素数の数をテストします。それは物事をかなりスピードアップするはずです。

別のアプローチは、最初にn / 2までのすべての素数を取得し、次にモジュラスが0かどうかを確認することです。 n までのすべての素数を取得するために使用するアルゴリズムは、こちら。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top