计算数组中的对,以使至少一个元素在C ++中为质数

给我们一个正整数数组。目的是找到具有至少一个素数成员的数组的不同元素对的计数。如果数组是[1,2,3,4],那么对将是(1,2),(1,3),(2,3),(2,4)和(3,4)。

让我们用例子来理解

输入− arr [] = {1,2,4,8,10};

输出-至少有一个元素为素数的数组中的对数为-4

说明-唯一的素数是2,将其与所有其他素数配对将得到-(1,2,,2,4),(2,8),(2,10)。

输入− arr [] = {0,1,4,6,15};

输出-至少有一个元素为素数的数组中的对数为-0

说明-数组没有素数元素。

以下程序中使用的方法如下

我们将创建一个数组arr_2 []来标记素数和非素数。如果arr_2 [i]为0,则i为质数,否则为非质数。如果对于任何一对,任何值arr_2 [A],arr_2 [B]为0,则对(A,B)对进行计数。

  • 取正整数的数组arr []。

  • 函数check_prime(int temp,int arr_2 []的值temp为最高,数组arr_2 []的arr_2 []填充为0的索引为质数,否则为1。

  • 将arr_2 [0] = arr_2 [1] = 0设置为0和1都不是素数。

  • 现在使用for循环,从i = 2遍历到i * i <temp。

  • 从j = 2 * i遍历到j <= temp和j + = i。为非素数设置arr_2 [j] = 1。

  • 函数Prime_Pairs(int arr [],int size)接受一个数组及其大小,并返回至少有一个元素为素数的此类对的计数。

  • 将初始计数设为0。

  • 将temp = * max_element(arr,arr + size)初始化为数组中的最大值。

  • 调用check_prime(temp,arr_2)。其中arr_2 []的初始化为0,长度为temp。

  • 现在我们将拥有arr_2 [],其中arr [i]对于i作为质数为0,对于i作为非质数为1。

  • 使用两个从i = 0到i <size和j = 0到j <size的for循环遍历数组。

  • 对于每对arr [i],arr [j]检查arr_2 [arr [i]] == 0或arr_2 [arr [j]] ==0。如果是,则递增计数。

  • 结果在所有循环结束时返回计数。

示例

#include <bits/stdc++.h>

using namespace std;

void check_prime(int temp, int arr_2[]){

   arr_2[0] = 1;

   arr_2[1] = 1;

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

      if (arr_2[i]==0){

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

            arr_2[j] = 1;

         }

      }

   }

}

int Prime_Pairs(int arr[], int size){

   int count = 0;

   int temp = *max_element(arr, arr + size);

   int arr_2[temp + 1];

   memset(arr_2, 0, sizeof(arr_2));

   check_prime(temp, arr_2);

   for (int i = 0; i < size; i++){

      for (int j = i + 1; j < size; j++){

         if (arr_2[arr[i]] == 0 || arr_2[arr[j]] == 0){

            count++;

         }

      }

   }

   return count;

}

int main(){

   int arr[] = { 3, 5, 2, 7, 11, 14 };

   int size = sizeof(arr) / sizeof(arr[0]);

   cout<<"Count of pairs in an array such that at least one element is prime are: "<<Prime_Pairs(arr, size);

   return 0;

}

输出结果

如果我们运行上面的代码,它将生成以下输出-

Count of pairs in an array such that at least one element is prime are: 15

以上是 计算数组中的对,以使至少一个元素在C ++中为质数 的全部内容, 来源链接: utcz.com/z/347117.html

回到顶部