c++ - 欧拉计画3-最高素数

在开始之前，我想澄清一下，我不是在寻找代码示例来获取答案；那将击败欧拉计划的目标。

可以在这里找到问题http://projecteuler.net/problem=3

我认为我有解决问题的方法，但是算法非常慢；它已经运行了将近两个半小时。因此，我正在寻找有关优化的一般建议。

谢谢。

#include<iostream>
using namespace std;

bool primality(int);

int main(){
  long long lim =  600851475143;
  long long div = lim/2;
  bool run = true;

  while(run){
    if(lim%div==0 && primality(div)){
      cout << "HPF: " << div;
      run = false;
    }
    else{
      div--;
    }
    if(div<=1){
      break;
    }
  }

  return 0;
}

bool primality(int num){
  for(int i=2; i<num; i++){
    if(num%i==0 && i!=num){
      return false;
    }
    else{
      return true;
    }
  }
}

最佳答案

如果您从2开始div而不是递减计数，然后在模数为零时将其从数字中除，那么您将获得两个有用的大优点：


您不必检查div是否为素数，因为它不能被合成，因为任何小于它的素数因子都已经被划分出来了。
每次找到一个因素时，您就可以减少剩余的问题大小，事实证明，输入数字的素数很小。


然后，一旦div*div大于剩余数，您也可能会中断，因为您知道此时必须是质数。这是因为任何大于平方根的除数都与小于平方根的除数“配对”。但是，由于这是一个“容易”的问题，因此此处不需要进行此优化（尽管对以后的问题很有用）。

关于c++ - 欧拉计画3-最高素数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8176928/