資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
