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