C++로 작성되어 배열에서 소수 쌍의 수를 찾습니다.

이 기사에서는 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

해결 방법을 찾는 방법

무차별 대입 방법

이제 가장 기본적인 방법, 즉 무차별 대입 방법에 대해 논의하고 다른 방법을 찾아 보겠습니다. 이 방법은 효율적이지 않습니다.

Example

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

Output

6

이 접근 방식에서는 각 요소가 소수인지 아닌지 알려주는 부울 배열을 만든 다음 가능한 모든 쌍을 반복하고 쌍의 두 숫자가 소수인지 여부를 확인합니다. . 소수인 경우 답을 1만큼 늘리고 계속하세요.

그러나 이 방법은 시간 복잡도가 O(N*N)이기 때문에 그다지 효율적이지 않습니다. 여기서 N은 배열의 크기이므로 이제 이 방법을 더 빠르게 만들고 싶습니다.

효율적인 방법

이 방법에서는 대부분의 코드가 동일하지만 중요한 변화는 가능한 모든 쌍을 반복하는 대신 공식을 사용하여 계산한다는 것입니다.

Example

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

Output

6

보시다시피 대부분의 코드는 이전 방법과 동일하지만, 복잡성을 크게 줄이는 주요 변경 사항은 우리가 사용하는 공식, 즉 n(n-1)입니다. /2 , 소수 쌍의 수를 계산합니다.

위 코드에 대한 설명

이 코드에서는 에라토스테네스의 체를 사용하여 대규모 배치가 될 때까지 모든 소수에 라벨을 붙입니다. 다른 부울 배열에서는 요소가 소수인지 여부를 인덱스로 표시합니다.

마지막으로 전체 배열을 반복하여 존재하는 총 소수 수를 찾고, 공식 n*(n-1)/2를 사용하여 가능한 모든 소수 쌍을 찾습니다. 이 공식을 사용하면 복잡성이 O(N)으로 줄어듭니다. 여기서 N은 배열의 크기입니다.

결론

이 기사에서는 배열에 존재하는 소수 쌍의 수를 O(n) 시간 복잡도로 찾는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 이 문제를 해결하는 완전한 방법(정상적이고 효율적인)을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다.

위 내용은 C++로 작성되어 배열에서 소수 쌍의 수를 찾습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!