数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律学在 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[]，并用 0 填充 arr_2[]，其中索引为素数，否则为 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] 为 0 表示 i 为素数，1 表示 i 为非素数。
使用两个 for 循环遍历数组，从 i=0 到 i<size 和 j=0 到 j<size。
对于每个数对 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
145 次查看
