이 기사에서는 C++를 사용하여 배열에서 소수 쌍의 수를 찾는 방법에 대한 모든 것을 설명합니다. 정수의 배열 arr[]이 있고 그 안에 있는 가능한 모든 소수 쌍을 찾아야 합니다. 여기 문제의 예가 있습니다 -
Input : arr[ ] = { 1, 2, 3, 5, 7, 9 }
Output : 6
From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)
Input : arr[] = {1, 4, 5, 9, 11}
Output : 1 해결책을 찾기 위한 접근 방식
무차별 대입 접근
이제 가장 기본적인 접근 방식인 Brute Force 접근 방식에 대해 논의하고 이 접근 방식은 그다지 효율적이지 않으므로 다른 접근 방식을 찾아보도록 하겠습니다.
예시
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(prime[i] == true && prime[j] == true)
answer++;
}
}
cout << answer << "\n";
return 0;
} 출력
6
이 접근 방식에서는 요소가 소수인지 여부를 알려주는 bool 배열을 만든 다음 가능한 모든 쌍을 살펴보고 쌍의 두 숫자가 모두 소수인지 확인합니다. 소수이면 답을 1씩 증가시키고 계속하십시오.
그러나 이 접근 방식은 시간 복잡도가 O(N*N)이므로 그다지 효율적이지 않습니다. , 여기서 N은 배열의 크기이므로 이제 이 접근 방식을 더 빠르게 만들 것입니다.
효율적인 접근
이 접근 방식에서는 대부분의 코드가 동일하지만 중요한 변경 사항은 가능한 모든 쌍을 사용하는 대신 공식을 사용하여 계산한다는 것입니다.
예시
#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
bool p[MAX+1];
memset(p, true, sizeof(p));
p[1] = false;
p[0] = false;
for(int i = 2; i * i <= MAX; i++){
if(p[i] == true){
for(int j = i*2; j <= MAX; j += i){
p[j] = false;
}
}
}
for(int i = 0; i < n; i++){
if(p[arr[i]] == true)
prime[i] = true;
}
}
int main(){
int arr[] = {1, 2, 3, 5, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]); // size of our array.
int answer = 0; // counter variable to count the number of prime pairs.
int MAX = INT_MIN; // Max element
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]);
}
bool prime[n]; // boolean array that tells if the element is prime or not.
memset(prime, false, sizeof(prime)); // initializing all the elements with value of false.
seiveOfEratosthenes(arr, prime, n, MAX);
for(int i = 0; i < n; i++){
if(prime[i] == true)
answer++;
}
answer = (answer * (answer - 1)) / 2;
cout << answer << "\n";
return 0;
} 출력
6
보시다시피 대부분의 코드는 이전 접근 방식과 동일하지만 복잡성을 크게 줄인 중요한 변경 사항은 우리가 사용한 공식, 즉 n(n-1)/2입니다. 소수 쌍.
위 코드 설명
이 코드에서는 에라토스테네스의 체를 사용하여 배열에 있는 Max 요소까지 모든 소수를 표시합니다. 다른 bool 배열에서는 요소가 소수인지 여부를 인덱스 방식으로 표시합니다.
마지막으로 전체 배열을 탐색하고 존재하는 총 소수의 수를 찾고 공식 n*(n-1)/2를 사용하여 가능한 모든 쌍을 찾습니다. 이 공식을 사용하면 복잡성이 O(N)으로 줄어듭니다. , 여기서 N은 배열의 크기입니다.
결론
이 기사에서는 O(n) 시간 복잡도에서 배열에 존재하는 소수 쌍의 수를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(보통 및 효율적)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.