计算数组中的对,以使至少一个元素在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