นับคู่ในอาเรย์ที่มีสมาชิกอย่างน้อยหนึ่งตัวเป็นจำนวนเฉพาะใน 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) รับอาเรย์และขนาด คืนจำนวนคู่ที่มีสมาชิกอย่างน้อยหนึ่งตัวเป็นจำนวนเฉพาะ
• กำหนด count เริ่มต้น 0
• เริ่มต้น temp=*max_element(arr, arr + size) เป็นค่าสูงสุดในอาเรย์
• เรียก check_prime(temp,arr_2) โดย arr_2[] เริ่มต้นเป็น 0 และมีความยาว temp
• ตอนนี้เรามี arr_2[] ที่ arr[i] เป็น 0 สำหรับ i เป็นจำนวนเฉพาะ และ 1 สำหรับไม่ใช่
• เดินทางอาเรย์ด้วยลูป FOR สองชั้น จาก i=0 ถึง i<size และ j=0 ถึง j<size
• สำหรับแต่ละคู่ arr[i], arr[j] ตรวจสอบถ้า arr_2[arr[i]] == 0 || arr_2[arr[j]] == 0 ถ้าจริงเพิ่ม count
• คืน count ท้ายสุดของลูปทั้งหมด

ตัวอย่างโค้ด C++

#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