请用c++代码编写如下问题的程序,如果一个素数是完美素数,当且仅当它的每一位数字只和也是一个素数,求〔1,n〕范围内完美素数的个数
时间: 2024-03-22 18:39:31 浏览: 60
基于C++的求素数
以下是求解完美素数个数的 C++ 代码,使用了筛素数和判断数字各位数之和是否为素数的方法:
```c++
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// 判断素数
bool is_prime(int n) {
if (n <= 1) return false;
int sqrtn = sqrt(n);
for (int i = 2; i <= sqrtn; i++) {
if (n % i == 0) return false;
}
return true;
}
// 判断各位数字之和是否为素数
bool is_sum_of_digits_prime(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return is_prime(sum);
}
int main() {
int n;
cin >> n;
// 筛素数
vector<bool> isPrime(n+1, true);
for (int i = 2; i <= sqrt(n); i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
// 统计完美素数的个数
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime[i] && is_sum_of_digits_prime(i)) {
count++;
}
}
cout << count << endl;
return 0;
}
```
其中,`is_prime` 函数用于判断一个数是否为素数,`is_sum_of_digits_prime` 函数用于判断一个数的各位数字之和是否为素数。在 `main` 函数中,首先读入输入的整数 `n`,然后使用筛素数的方法求出 `[1, n]` 范围内的所有素数,最后统计出完美素数的个数并输出。
阅读全文