这是我从Euler项目对Problem 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)使用Sieve of Eratosthenes算法预先生成质数。在这个简单的示例中可能不值得。
最佳答案
好的,这是我的看法。希望它可能有用(编辑:不要引起“不要使用下划线”注释-添加了名称空间)。
编辑#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
编号,带-O3,Linux,Intel i5 Core的GCC 4.7.2中循环测试。时间如下(大约):get_factor_prime
比OP解决方案快3
倍;get_factor_prime_faster
比OP解决方案快6
倍。关于c++ - 欧拉计划3(演出),我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/16245976/