1

これは、Project Euler の問題 3に対する私の解決策です。ソリューションをより効率的にする方法はありますか?

int largestPrimeFactor(unsigned _int64 x) 
{
   unsigned __int64 remainder = x;
   int max_prime;

   for (int i = 2; i <= remainder; i++)
   {
       while(remainder%i==0) {
           remainder /= i;
           max_prime = i;
       }
   }
    return max_prime;
}

更新:提案をありがとうございました。それらに基づいて、次のようにアルゴリズムを変更しました。

1) 除数の候補もスキップします。

while(remainder%2==0) {
    max_prime  = 2;
    remainder /= 2;     
}

for (int i = 3; i <= remainder; i += 2)
{
    while(remainder%i==0) {
        max_prime  = i;
        remainder /= i;         
    }
}

2) 剰余の平方根まで計算します。

for (int i = 2; i*i <= remainder; i++)
{
    while(remainder%i==0) {
        max_prime  = i;
        remainder /= i;
        cout << i << " " << remainder << endl;
    }
}
if (remainder > 1) max_prime = remainder;

3)エラトステネスのふるいアルゴリズムを使用して事前に素数を生成します。この単純な例ではおそらく価値がありません。

4

2 に答える 2

0

一般的なアプローチ:

ステップ 1:エラトステネスのふるいアルゴリズムを使用して、ceil(sqrt(number)) までの素数を生成します。
ステップ 2: これらを使用して数を因数分解します。

于 2013-04-26T22:26:36.523 に答える
0

わかりました、これが私の見解です。それが役立つことを願っています（編集：「先頭のアンダースコアを使用しないでください」というコメントを誘発しないように-名前空間を追加しました）。編集 #2:get_factor_prime_faster()ヘルパー関数を使用してより高速な関数を追加しました。最後に速度テストに関するメモを参照してください。

#include <cstdint>
#include <iostream>

namespace so
{
// Head-on approach: get_factor_prime()
std::uint64_t get_factor_prime( std::uint64_t _number )
{
 for( std::uint64_t i_ = 2; i_ * i_ <= _number; ++i_ ) 
  if( _number % i_ == 0 )
   return ( get_factor_prime( _number / i_ ) );

 return ( _number );
}

// Slightly improved approach: get_factor_prime_faster() and detail::get_factor_prime_odd()
namespace detail
{
std::uint64_t get_factor_prime_odd( std::uint64_t _number )
{
 for( std::uint64_t i_ = 3; i_ * i_ <= _number; i_ += 2 )
  if( _number % i_ == 0 )
   return ( get_factor_prime_odd( _number / i_ ) );

 return ( _number );
}
} // namespace so::detail 

std::uint64_t get_factor_prime_faster( std::uint64_t _number )
{
 while( _number % 2 == 0 )
  _number /= 2;

 return ( detail::get_factor_prime_odd( _number ) );
}
} // namespace so

int main()
{
 std::cout << so::get_factor_prime( 600851475143 ) << std::endl;
 std::cout << so::get_factor_prime( 13195 ) << std::endl;
 std::cout << so::get_factor_prime( 101 ) << std::endl;

 std::cout << so::get_factor_prime_faster( 600851475143 ) << std::endl;
 std::cout << so::get_factor_prime_faster( 13195 ) << std::endl;
 std::cout << so::get_factor_prime_faster( 101 ) << std::endl;

 return( 0 );
}

プログラム出力:

6857
29
101
6857
29
101

確かに、数値が素数かどうかを簡単に確認する方法はまだわかりません...

600851475143 * 1024編集:番号、GCC 4.7.2、-O3、Linux、Intel i5 Coreのループでテスト済み。時間は次のとおりです（およそ）。

get_factor_primeOPのソリューションよりも3数倍高速です。

get_factor_prime_faster6OPのソリューションよりも数倍高速です。

于 2013-04-26T23:41:36.780 に答える