算法-数学-之完全数的计算

算法-数学-之完全数的计算

分析与思路:

直接从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 //点评:此程序比我的程序代码量减少一半,而且效率高了很多,值得学习

 

上一篇:面向C/C++的json解析和合成的第三方库cJson


下一篇:vue如何直接加载本地json文件