C++ 筛选法：求各位数字之和为奇数的素数。 |21xrx.com

2023-06-22 18:21:50 深夜i -- --

C++ 筛选法各位数字之和奇数素数

C++是一种强大的编程语言，具有很多优秀的算法，其中一种算法是筛选法。利用这种算法，我们可以找出给定范围内的所有素数，并得到各位数字之和为奇数的素数，下面我们就来具体了解一下如何用C++实现这个算法。

首先我们需要声明一个布尔数组，用于存储给定范围内的素数情况。假设数组名为isPrime，数组大小为MAX，表示从2到MAX-1这个区间内的数字是否为素数。那么我们可以初始化这个数组，将所有数都看作素数，然后从2开始，依次筛掉合数。

这个过程可以用一个for循环来实现，具体代码如下：

for(int i = 2; i*i <= MAX; ++i) {

if(isPrime[i]) {

for(int j = i*i; j <= MAX; j += i) {

isPrime[j] = false;

}

其中，i代表当前素数，j代表i的倍数，从i的平方开始枚举，每次加上i。一旦发现一个素数i，就把它的倍数都标记为合数，直到i的平方大于MAX为止。

接下来就是筛选出各位数字之和为奇数的素数，我们需要定义一个函数可以计算数字之和，在使用for循环对所有素数进行遍历，将各位数字之和进行计算，再判断是否为奇数，如果是的话就把该素数输出。

整个算法实现如下：

// 声明一个布尔型的数组isPrime

const int MAX = 1000000;

bool isPrime[MAX];

// 求一个数n的各位数字之和

int digitSum(int n) {

int res = 0;

while(n) {

res += n % 10;

n /= 10;

}

return res;

}

int main() {

// 初始化isPrime数组，全部赋值为true

memset(isPrime, true, sizeof(isPrime));

// 利用筛选法求出所有素数情况

for(int i = 2; i*i <= MAX; ++i) {

if(isPrime[i]) {

for(int j = i*i; j <= MAX; j += i) {

isPrime[j] = false;

}

// 筛选出各位数字之和为奇数的素数

for(int i = 2; i <= MAX; ++i) {

if(isPrime[i] && digitSum(i) % 2 == 1)

cout << i << " ";

}

return 0;

}

通过以上代码，我们就可以求出给定范围内的各位数字之和为奇数的素数了。该算法具有良好的时间复杂度和空间复杂度，适用于各种规模的数字求解，可以在实际生活中大大方便人们的求解工作。

上一篇: idea打包java可执行jar包

下一篇: C++编程需要下载哪些软件？

相似文章