欧拉计划 3(性能) [英] Project Euler 3 (performance)

问题描述

这是我对来自 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.

这篇关于欧拉计划 3(性能)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！