นับคู่ในอาร์เรย์ที่มีอย่างน้อยหนึ่งองค์ประกอบที่เป็นจำนวนเฉพาะใน 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 แสดงว่าฉันเป็นไพรม์อย่างอื่นที่ไม่ใช่ไพรม์ หากสำหรับคู่ใดค่าใด ๆ 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 loop ให้เคลื่อนที่จาก i=2 ไปยัง i*i

• ข้ามจาก 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 และมีอุณหภูมิความยาว

• ตอนนี้เราจะมี arr_2[] โดยที่ arr[i] เป็น 0 สำหรับฉัน เป็นไพรม์ และ 1 สำหรับฉัน เป็น non-prime

• อาร์เรย์การเคลื่อนที่โดยใช้สองลูปจาก i=0 ถึง i

• สำหรับแต่ละคู่ 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