欧拉计划 3(性能)

本文介绍了欧拉计划 3(性能)的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是我对来自 Project Euler 的问题 3 的解决方案.有什么办法可以使解决方案更有效吗?

This is my solution to Problem 3 from Project Euler. Is there any way how to make the solution more efficient?

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

更新:感谢大家的建议.基于它们，我修改了算法如下:

Update: Thank you all for the proposals. Based on them I modified the algorithm as follows:

1) 甚至跳过候选除数.

1) Skip even candidate divisors.

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) 计算余数的平方根.

2) Work up to square root of remainder.

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) 使用 Eratosthenes 筛分 算法预先生成素数.在这个简单的例子中可能不值得.

3) Generate prime numbers in advance using Sieve of Eratosthenes algorithm. Probably not worth in this simple example.

推荐答案

常用方法:

第 1 步:使用 埃拉托色尼筛法 生成高达 ceil(sqrt(number)) 的素数a> 算法.第 2 步:使用这些来分解数字.

Step 1: Generate prime numbers up to ceil(sqrt(number)) using the Sieve of Eratosthenes algorithm. Step 2: Use these to factor the number.