C++代码素数是指一个大于1的自然数,除了1和此整数自身外,不能被其他自然数整除的数。如果一个素数是完美的素数,当且仅当它的每一位数字之和也是一个素数。如29,本身是素数,而且2+9 = 11也是素数,所以它是完美素数。求[1,n]范围内完美素数的个数。
时间: 2024-03-23 10:38:35 浏览: 38
c++两种方法求素数
5星 · 资源好评率100%
好的,以下是一个C++代码示例来实现这个算法:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
bool is_prime(int num) {
if (num <= 1) {
return false;
}
for (int i = 2; i <= sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
int sum_of_digits(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}
int count_perfect_primes(int n) {
int count = 0;
for (int i = 2; i <= n; i++) {
if (is_prime(i) && is_prime(sum_of_digits(i))) {
count++;
}
}
return count;
}
int main() {
int n;
cout << "Enter the value of n: ";
cin >> n;
cout << "Number of perfect primes in [1, " << n << "]: " << count_perfect_primes(n) << endl;
return 0;
}
```
在这个代码中,`is_prime()`函数用于检查一个数是否为素数,`sum_of_digits()`函数用于计算一个数的数字之和,`count_perfect_primes()`函数用于计算[1,n]范围内完美素数的个数。我们可以在`main()`函数中调用`count_perfect_primes()`函数并传入一个整数n作为参数,它将返回[1,n]范围内完美素数的个数。
请注意,这个算法的时间复杂度为O(n log n),因为我们需要检查每个数字是否为素数,并计算它们的数字之和是否为素数。对于更大的n,这个算法可能会比较慢。
阅读全文