项目欧拉3 - 最高素数因素

Question

在我开始之前,我想澄清一点,我不是在寻找代码示例来获得答案; 这会击败欧拉计划的目标.

问题可以在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;
    }
  }
}

Answer 1

如果从div2 开始计算而不是向下计数,并在模数为零时将其除以数字,则可以获得两个有用的优点:

1. 您不必检查是否div为素数,因为它不能是复合的,因为任何小于它的素数因子都已经被分割出来.
2. 每次找到一个因子时,您都会减少剩余的问题大小,而事实证明,输入数字具有相当小的素数因子.

然后你可以打破一次div*div大于剩余的数字,因为你知道那时它必须是一个素数.这是因为任何大于平方根的除数都与一个小于平方根的"配对".但是,由于这是一个"简单"的问题,因此这里不需要进行此优化(尽管它对以后的问题很有用).