京东笔试C++到怀疑人生,第二题运行0%,求大家看看怎么回事
测试用例可以通过,自己测试了几个其他的数值也可以。
这种方法时间复杂度有点高,但是0% 实在是想不明白。
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int dft(int num)
{
if(num == 1)
return 0;
if(num == 2)
return 1;
int count;
int sqrtnum = (int)sqrt(num); //开方
int a = 1;
for(int i=sartnum; i>=1; i--)
{
if(num % i == 0)
{
a = i;
break;
}
}
if(a != 1) //不为质数
count = dft(num/a) + dft(a);
else
count = dft(num - 1);
return count+1;
}
int main()
{
int n;
cin>>n;
vector<int>v(n);
for(int i=0; i<n; i++)
cin>>v[i];
int countSum = 0;
for(int i=0; i<n; i++)
countSum = countSum + dft(v[i]);
cout<<countSum;
return 0;
} 

