양의 정수 배열이 제공됩니다. 목표는 최소 하나의 소수 구성원을 갖는 배열의 고유한 요소 쌍의 수를 찾는 것입니다. 배열이 [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[]를 소수 else 1로 인덱스에 대해 0으로 채웁니다.
-
0과 1이 모두 소수가 아니므로 arr_2[0]=arr_2[1]=0으로 설정합니다.
-
이제 for 루프를 사용하여 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으로 초기화되고 길이는 temp입니다.
-
이제 우리는 arr_2[]를 갖게 될 것입니다. 여기서 arr[i]는 i의 경우 0이고 소수가 아닌 경우 1입니다.
-
i=0에서 i
까지 2개의 for 루프를 사용하여 배열을 탐색합니다. -
각 쌍 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