Question

C++一道简单算法题，大佬们看下为什么我的代码不能满分通过？

#include <bits/stdc++.h>using namespace std;int main(){ int n; int maxNum = 0; cin >> n; for(int i = 2;i < sqrt(n);i++){ for(int j = i;j < n;j++){ if(i * j == n){ if(j > maxNum){ maxNum = j; } } } } cout << maxNum; return 0;}//其中有个测试文件没通过是这样的：输入1999520027，输出99991//可是我输入1999520027后，没有任何输出结果？不知道为什么？求指教！谢谢大佬们！

Answer 1

C++算法题：

按题目的意思n<=2*10^9

图中红色框内代码i*j是有可能超过这个范围的，造成整数最大溢出得不到正确结果。应该改为一个for循环，从最大的数开始往小的数搜索，不要用乘法，用除法。

for(int i = n-1; n >= sqrt(n); i--)

{

if(n%i==0)

maxNum= i;

break;

}

当然这些要保证输入的n一定得满足只有两个质数相乘等于n,不然需要增加判断是否为质数。

Answer 2

你这代码复杂度太高了
大致估算了一下，O(sqrt(n)*n)
n的数据范围[0,10^9]，肯定时超时了
一般编程题目中，数据范围超过10^6，O(n)的算法就有超时的可能了
我写了一个稍微快点的，复杂度大概O(sqrt(n)*sqrt(i))，应该小于O(n)
你试一下
/****************************/
#include <bits/stdc++.h>
using namespace std;
bool isp(int x){//O(sqrt(n))
//用O(sqrt(n))的方法判断一个数是否为素数
if(x<2){
return false;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
int main() {
int n;
cin >> n;
for(int i=2;i<=sqrt(n);i++){//O(sqrt(n)*sqrt(i))<O(n)
/*
遍历O(sqrt(n))
n%i==0：n能整除i
isp(i)：判断i是否为素数
isp(n/i)：判断n/i是否为素数
*/
if(n%i==0&&isp(i)&&isp(n/i)){
//3个条件都满足，输出n/i，n/i就是大素数
cout<<n/i<<endl;
break;//提前结束
}
}
return 0;
}

Answer 3

不是没有任何输出，是这个算法效率比较低，计算量太大，只要你愿意等，还是会出结果的，不过这个等的时间会随数字越大，时间越来越长。
我给改了下思路，时间会明显缩短的。下面的代码自己体会下吧。
//====== 以下是代码 ======//

//其中有个测试文件没通过是这样的：输入 1999520027，输出99991//可是我输入1999520027后，没有任何输出结果？不知道为什么？
//#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector <int> array_a,array_b;

int IsPrime(int n)
{
int tail;

if(n>=10)
{
tail = n%10;

if(tail == 1 || tail==3 || tail==7 || tail==9)
{
int tmp = n;
int bit=0,bit_sum=0;
while(tmp>0)
{
bit = tmp % 10;
tmp = tmp / 10;
bit_sum += bit;
}
if(bit_sum % 3)
{
for(int i=11;i<n/2;i++)
{
if(!(n%i))
return 0;
}

cout<<".";
return 1;
}
else
return 0;
}
}
else
{
if(n == 1 || n== 2 || n==3 || n==5 || n==7)
return 1;
}

return 0;
}

int main(int argc,char** argv)
{
int n;
int max = 0;

cout<<"please input a number:"<<endl;
cin>>n;

//calculte array_a
array_a.clear();
for(int i=0;i<sqrt(n);i++)
{
if(IsPrime(i))
array_a.push_back(i);
}

array_b.clear();
for(int i=0;i<array_a.size();i++)
{
if(!(n % array_a[i]))
array_b.push_back(n/array_a[i]);
}

for(int i=0;i<array_b.size();i++)
{
if(IsPrime(array_b[i]))
if(array_b[i]>max)
max = array_b[i];
}
cout<<endl;
cout<<"Max prime is "<<max<<endl;

system("pause");

return 0;
}