项目Euler 3-最高素数因子
项目Euler 3-最高素数因子
提问于 2011-11-18 02:04:46
在开始之前，我想澄清一下，我是，而不是，我在寻找得到答案的代码示例；这将击败Project的对象。
这个问题可以在这里找到，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
Stack Overflow用户
回答已采纳
发布于 2011-11-18 02:15:58
如果您从2开始启动div，然后向上计数而不是向下计数，并在模数为零时将其从数字中除以，那么您将获得两大优势，它们在这里非常有用：
- 您不必检查
div是否为素数，因为它不能合成，因为任何比它小的素因子都会被除开。 - 每次找到一个因子，就会缩小剩余的问题大小，而且，结果表明，输入数字有相当小的素数。
然后，当div*div大于剩余的数时，您也可以中断，因为在这一点上，它必须是素数。这是因为任何大于平方根的除数都与小于平方根的除数“配对”。但是，由于这是一个“容易”的问题，因此这里不需要这种优化(尽管它对于以后的问题很有用)。
Stack Overflow用户
发布于 2012-10-17 18:33:59
# Possible solution but still its *time consuming* but answer can be guessed by the last option in console output
#include<stdio.h>
#include<string>
#include<iostream>
#include<math.h>
int prime(unsigned long long);
using namespace std;
int main(){
unsigned long long ii, ij; unsigned long long in;
cin>>in; ij = ceil(in/2);
if( (ij % 2) == 0 ) ij -= 1;
for(ii = 3 ;ii < ij;ii+= 2){
if(in % ii == 0){
if(prime(ii) == 1 ){
cout<<" ans "<<ii<<endl;
}
}
}
return 0;
}
int prime(unsigned long long ii){
unsigned long long ij;
for(ij = 3;ij < ii/2 ;ij += 2){
if( (ii % ij) ==0){
return 0;
}
}
return 1;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8176928
复制相关文章
相似问题
腾讯云开发者
