京东笔试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; }