c# - Project Euler の質問 3 のヘルプ

Question

私は 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();
    }

score 15 · Accepted Answer

まず、n / 2 から検索を開始するのではなく、n の平方根から検索を開始します。因数の半分が得られ、残りの半分は補数になります。

例えば：

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.

score 10 · Accepted Answer

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;

これは十分に速いはずです...注意、素数をチェックする必要はありません...

score 10 · Accepted Answer

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

score 10 · Accepted Answer

実際、この場合、素数性をチェックする必要はありません。見つけた要素を削除するだけです。n == 2 から始めて、上に向かってスキャンします。Evil-big-number % n == 0 の場合、evil-big-number を n で割り、小さい evil-number を続けます。n >= sqrt(big-evil-number) のときに停止します。

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

score 6 · Accepted Answer

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

より良いアプローチについては、エラトステネスのふるいを読んでください...正しい方向に向けられるはずです。

score 3 · Accepted Answer

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) を返します。

score 2 · Accepted Answer

答えが見つかったら、ブラウザに次のように入力してください ;)

http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)

Wofram Alpha はあなたの友達です

score 2 · Accepted Answer

p私が行った方法は、エラトステネスの篩を使用して、2 から始まる素数 ( ) を検索することでした。このアルゴリズムは、かなり高速なマシンで 2 秒未満で 1000 万未満のすべての素数を見つけることができます。

見つかった素数ごとに、整数除算ができなくなるまで、テスト対象の数値に分割してテストします。(つまり、チェックn % p == 0して true の場合は除算します。)

一度n = 1、完了です。分割に成功した最後の値nがあなたの答えです。n補足として、途中ですべての素因数を見つけました。

PS: 前に述べたように、の間の素数のみを検索する必要があります2 <= n <= sqrt(p)。これにより、エラトステネスのふるいは非常に高速で実装が簡単なアルゴリズムになります。

score 1 · Accepted Answer

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

score 1 · Accepted Answer

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

score 1 · Accepted Answer

Java で再帰アルゴリズムを使用すると、1 秒もかからずに実行されます...アルゴリズムには、排除できる「ブルートフォーシング」が含まれているため、少し考えてみてください。また、中間計算によって解空間がどのように縮小されるかも見てください。

score 0 · Accepted Answer

あなたはこれを見たいかもしれません： Xが素数であるかどうかを決定することができ、単なる人間のプログラマーを混乱させない簡単なアルゴリズムはありますか？

そして私はlill泥の解決策が好きです：

require "mathn.rb"
puts 600851475143.prime_division.last.first

ここで確認しました

score 0 · Accepted Answer

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

score -1 · Accepted Answer

Miller-Rabin Primality Testを使用して、数値が素数であるかどうかをテストしてみてください。これにより、処理が大幅に高速化されるはずです。

score -1 · Accepted Answer

もう 1 つの方法は、最初に n/2 までのすべての素数を取得してから、モジュラスが 0 であるかどうかを確認することです。nまでのすべての素数を取得するために使用するアルゴリズムは、こちらにあります。

c# - Project Euler の質問 3 のヘルプ

16 に答える 16

Related

Reference