输入一个整数n,计算n的所有因子(不包括1与自身)之和
时间: 2023-05-30 08:01:35 浏览: 127
算法1:暴力枚举
直接从2到n-1枚举每个数,判断是否是n的因子,如果是则加入到因子之和中。
时间复杂度:O(n)
C++ 代码
```cpp
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
for (int i = 2; i <= n - 1; i++) {
if (n % i == 0) {
sum += i;
}
}
cout << sum << endl;
return 0;
}
```
算法2:优化枚举
由于一个数的因子一定是小于等于其一半的,因此只需要枚举2到n/2即可。
时间复杂度:O(n/2)
C++ 代码
```cpp
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
for (int i = 2; i <= n / 2; i++) {
if (n % i == 0) {
sum += i;
}
}
cout << sum << endl;
return 0;
}
```
算法3:优化枚举(进一步优化)
由于一个数的因子一定是小于等于其平方根的,因此只需要枚举2到sqrt(n)即可。同时为了避免浮点数的运算,可以将i*i与n比较。
时间复杂度:O(sqrt(n))
C++ 代码
```cpp
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
int sqrtn = sqrt(n);
for (int i = 2; i <= sqrtn; i++) {
if (n % i == 0) {
sum += i;
if (i * i != n) {
sum += n / i;
}
}
}
cout << sum << endl;
return 0;
}
```
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)