Đếm các cặp trong một mảng sao cho ít nhất một phần tử là số nguyên tố trong C ++

Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là để tìm số lượng các cặp phần tử khác nhau của một mảng có ít nhất một phần tử nguyên tố. Nếu mảng là [1,2,3,4] thì các cặp sẽ là (1,2), (1,3), (2,3), (2,4) và (3,4).

Hãy cho chúng tôi hiểu với các ví dụ

Đầu vào - arr [] ={1,2,4,8,10};

Đầu ra - Đếm các cặp trong một mảng sao cho ít nhất một phần tử là số nguyên tố là - 4

Giải thích - Phần tử nguyên tố duy nhất là 2 và ghép nối nó với tất cả các phần tử khác sẽ cho - (1,2), (2,4), (2,8), (2,10).

Đầu vào - arr [] ={0,1,4,6,15};

Đầu ra - Đếm các cặp trong một mảng sao cho ít nhất một phần tử là số nguyên tố là - 0

Giải thích - Mảng không có phần tử nguyên tố.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Chúng tôi sẽ tạo một mảng arr_2 [] để đánh dấu số nguyên tố và không phải số nguyên tố. Nếu arr_2 [i] là 0 thì tôi là số nguyên tố khác không phải là số nguyên tố. Nếu đối với bất kỳ cặp nào thì giá trị arr_2 [A], arr_2 [B] là 0 thì cặp (A, B) được tính.

Lấy một mảng arr [] của các số nguyên dương.
Hàm check_prime (int temp, int arr_2 [] nhận một giá trị tạm thời là cao nhất và một mảng arr_2 [] và điền arr_2 [] với 0 cho chỉ mục là số nguyên tố khác 1.
Đặt arr_2 [0] =arr_2 [1] =0 vì cả 0 và 1 đều không phải là số nguyên tố.
Hiện đang sử dụng vòng lặp for, chuyển từ i =2 sang i * i
Chuyển từ j =2 * i sang j <=temp và j + =i. Đặt arr_2 [j] =1 cho các số không phải số nguyên tố.
Hàm Prime_Pairs (int arr [], int size) nhận một mảng và kích thước của nó và trả về số lượng các cặp như vậy, trong đó ít nhất một phần tử là nguyên tố.
Lấy số lượng ban đầu là 0.
Khởi tạo temp =* max_element (arr, arr + size) làm giá trị lớn nhất giữa các mảng.
Gọi check_prime (tạm thời, arr_2). Trong đó arr_2 [] được khởi tạo bằng 0 và có độ dài tạm thời.
Bây giờ chúng ta sẽ có arr_2 [] trong đó arr [i] là 0 đối với tôi là số nguyên tố và 1 đối với tôi là số không phải số nguyên tố.
Traverse mảng sử dụng hai vòng lặp for từ i =0 đến i
Đối với mỗi cặp arr [i], arr [j] hãy kiểm tra xem arr_2 [arr [i]] ==0 hay arr_2 [arr [j]] ==0. Nếu có thì hãy đếm gia số.
Kết quả là số lượng trả về ở cuối tất cả các vòng lặp.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

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