c++ - 欧拉计划 3（性能）

Question

这是我对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) 使用埃拉托色尼筛算法提前生成素数。在这个简单的例子中可能不值得。

Answer 1

一种常见的方法：

第 1 步：使用埃拉托色尼筛算法生成直到 ceil(sqrt(number)) 的素数。
第2步：使用这些来分解数字。

Answer 2

好的，这是我的看法。希望它可能有用（编辑：不要激起“不要使用前导下划线”评论 - 添加了一个命名空间）。get_factor_prime_faster()编辑#2：使用辅助函数添加了一个更快的函数。最后请参阅有关速度测试的说明。

#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_prime比3OP 的解决方案快几倍；

get_factor_prime_faster比6OP 的解决方案快几倍。