c++编写:如果有一个正整数N,能被2520整除,则N就是完美数。 现有一个非常大的正整数M,最高位为1,其余均为0,请计算在[1,M][1,M]范围内有多少个完美数。 输入:输入一个正整数M 输出:完美数的个数
时间: 2024-02-05 09:11:15 浏览: 76
这道题需要用到数论的知识,首先要了解什么是完美数。完美数是指除自身之外的所有因子之和等于自身的数,例如6就是一个完美数,因为6的因子为1,2,3,而1+2+3=6。
而题目中要求的是能被2520整除的数,也就是说,它的因子包括1,2,3,4,5,6,7,8,9,10,12,14,15,18,20,21,24,28,30,35,36,40,42,45,56,60,63,70,72,84,90,105,120,126,140,168,180,210,252,280,315,360,420,504,630,840,1260,2520。
根据这个因子列表,我们可以发现2520本身也是一个完美数,因此只需要计算[1,M]区间内2520的倍数个数即可。假设M的位数为n,那么M最多有n个0,因此最多有10^n个数字。而2520是4个质数2,3,5,7的乘积,因此至少包含4个不同的质因子,因此[1,M]区间内能被2520整除的数最多有10^(n-4)个。因此我们可以使用循环,每次加上10^(n-4)即可。
以下是C++代码实现:
```c++
#include <iostream>
#include <cmath>
using namespace std;
int main() {
long long M; // 注意要用long long类型,因为输入的数可能很大
cin >> M;
int cnt = 0; // 记录完美数个数
for (long long i = 2520; i <= M; i += 2520) { // 只考虑2520的倍数
int sum = 1; // 因子之和初始化为1
for (int j = 2; j <= sqrt(i); j++) {
if (i % j == 0) {
sum += j;
if (j != i / j) {
sum += i / j;
}
}
}
if (sum == i) {
cnt++;
}
}
cout << cnt << endl;
return 0;
}
```
注意,由于题目中给出的M最高位为1,因此输入的数至少为10^(n-1),因此可以忽略掉比2520小的数,直接从2520开始循环。
阅读全文