如果有一个正整数N,能被2520整除,则N就是完美数。 现有一个非常大的正整数M,最高位为1,其余均为0,请用C++语言计算在[1,M]范围内有多少个完美数。
时间: 2023-08-13 15:04:56 浏览: 45
这道题需要用到一些数学知识和编程技巧。首先我们需要知道2520是由2、3、5、7的幂次组成的,它是整数1到10的最小公倍数。因此,如果一个数能被2520整除,那么它一定也能被2、3、5、7整除。
我们可以用一个数组来记录1到M中每个数是否能被2、3、5、7整除。然后用一个循环遍历1到M中的每个数,如果能被2、3、5、7整除,就说明它是完美数,统计计数器即可。
具体实现如下:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 1e9; // 最大范围
bool isDivisible[MAXN]; // 是否能被2、3、5、7整除
int main() {
memset(isDivisible, false, sizeof(isDivisible)); // 初始化为false
isDivisible[0] = true; // 特判0
for (int i = 2; i <= 7; i++) { // 2、3、5、7必须特判
for (int j = i; j <= MAXN; j += i) {
isDivisible[j-1] = true; // 标记能被i整除的数
}
}
long long cnt = 0; // 完美数的数量
for (int i = 2520; i <= MAXN; i += 2520) { // 从2520开始遍历
bool isPerfect = true;
for (int j = 2; j <= 7; j++) {
if (!isDivisible[(i/j)-1]) { // 判断是否能被2、3、5、7整除
isPerfect = false;
break;
}
}
if (isPerfect) cnt++;
}
cout << cnt << endl;
return 0;
}
```
这里需要注意的是,题目中的M是非常大的,因此需要用long long类型来存储完美数的数量。另外,由于数组的下标是从0开始的,因此需要将每个数减去1才能正确标记。