分析与思路:
直接从1到输入的整数之间进行遍历,把每个数从1到n/2之间进行整除。(因为每个数最大的除数不会超过自身的一半(其实还有更小的除数,就是平方根。后面会提及),然后将整除后的商与除数累积起来。判断是否等于自身即可。于是写出了以下代码:
1 #include <iostream> 2 #include <vector> 3 #include "numeric" 4 using namespace std; 5 bool JudgeResult(int value) 6 { 7 vector<int> result; 8 if (value < 1) 9 { 10 return false; 11 } 12 13 for (int i = 2; i <= value / 2; i++) 14 { 15 if (value%i == 0) 16 { 17 //int divided_value = value / i; 18 result.push_back(i); 19 continue; 20 } 21 } 22 23 int sum = 0; 24 // for (int i = 0; i < result.size(); i++)//这里应该有一个方便的运算方法,什么accum啥的 25 // { 26 // sum += result[i]; 27 // } 28 29 // sum += 1; 30 sum=accumulate(result.begin(), result.end(), 1); 31 result.clear(); 32 if (sum == value) 33 { 34 return true; 35 } 36 else 37 { 38 return false; 39 } 40 } 41 int main() 42 { 43 bool judgeresult = false; 44 45 int n=0; 46 while( cin>>n) 47 { 48 int count = 0; 49 50 for (int i = 2; i <= n; i++) 51 { 52 judgeresult = JudgeResult(i); 53 if (judgeresult == 1) 54 { 55 count++; 56 //std::cout << i << "\n"; 57 } 58 59 } 60 std::cout <<count << "\n"; 61 } 62 63 64 }
点评:用了一个vector保存结果,其实有点多余。同时,当输入的数据大于等于500000时,会出现超时。改进点有2点,一个是去掉vector,直接判断即可。第二,缩小判别边界,n/2改成sort(n),时间一下子缩小很多,输入数据是500000时,也不会出现超时情况,
代码如下:
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 int main() { 6 int n; 7 int sum; 8 int count; 9 int j; 10 while (cin >> n) { 11 count = 0; 12 for (int i = 2; i < n; i++) { 13 // i = 6; 14 sum = 0; 15 j = sqrt(i);//巧妙,设定区间也很方便,快捷高效很多,同时知道求根号取值不方便,采用开平方的方法解决这个问题 16 while (j) { 17 if (i%j == 0) 18 sum = sum + j + i / j; 19 j--; 20 } 21 if (sum - i == i) //这里因为上面加了该数本身,因此要减去自身,即(sum - i)---因为当j=1的时候,i/j==i,相当于把i加进去了,所以要减去i 22 count++; 23 } 24 cout << count << endl; 25 } 26 27 return 0; 28 } 29 //点评:此程序比我的程序代码量减少一半,而且效率高了很多,值得学习