C++ 각 요소 쌍의 합이 소수인 최대 하위 집합

주어진 배열에서 각 요소 쌍의 합이 소수인 가장 큰 부분 집합을 찾습니다. 예를 들어 최대 요소가 100000이라고 가정합니다. −

Input: nums[ ] = { 3, 2, 1,1 }
Output: size = 3, subset = { 2, 1, 1 }
Explanation:
Subsets can be formed: {3, 2}, {2, 1} and { 2, 1, 1},
In {2, 1, 1} sum of pair (2,1) is 3 which is prime,
and the sum of pairs (1,1) is 2 which is also a prime number.

Input: nums[ ] = {1, 4, 3, 2}
Output: size = 2, subset = {1, 4}
Explanation:
subset can be formed: {1, 4}, {4, 3}, and {3, 2}
All are of size 2 so we can take any subset like 1 + 4 =5 which is a prime number.

해를 찾는 방법

먼저 숫자 쌍이 소수인지 확인하려면 짝수는 소수가 아니므로 그 합이 홀수인지 짝수인지 확인해야 합니다. 2를 제외하고. 또한 두 숫자가 모두 홀수이거나 짝수인 경우 그 합은 짝수일 수 있습니다.

이 문제에서는 x, y, z 세 개의 숫자를 사용하며, 그 중 두 개는 홀수이거나 짝수여야 합니다. 그런 다음 이 하위 집합에 소수의 쌍이 포함되어 있는지 확인합니다. 이는 다음과 같은 경우에 가능할 수 있습니다.

• 하위 집합에는 1의 일부 숫자와 NUM + 1이 소수여야 하는 다른 숫자가 포함되어 있습니다.

• 또는 하위 집합에 두 개의 숫자만 포함된 경우 그 합은 소수입니다.

Example

 #include <bits/stdc++.h>
using namespace std;
#define M 100001
bool check_prime[M] = { 0 };
int sieve_of_eratosthenes(){
    for (int p = 2; p * p < M; p++){
       // If it is not marked then mark
        if (check_prime[p] == 0){
            // Update all multiples of p
            for (int i = p * 2; i < M; i += p)
                check_prime[i] = 1;
        }
    }
    return 0;
}
int main(){
    sieve_of_eratosthenes();
    int nums[] = {  3, 2, 1, 1};
    int n = sizeof(nums) / sizeof(nums[0]);
        int ones = 0;
    for (int i = 0; i < n; i++)
        if (nums[i] == 1)
            ones++;
    // If ones are present and
    // elements greater than 0 are also present
    if (ones > 0){
        for (int i = 0; i < n; i++){
            //checking whether num + 1 is prime or not
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
                cout << ones + 1 << endl;
                // printing all the ones present with nums[i]
                for (int j = 0; j < ones; j++)
                cout << 1 << " ";
                cout << nums[i] << endl;
                return 0;
            }
        }
    }
    // If subsets contains only 1&#39;s
    if (ones >= 2){
        cout << ones << endl;
        for (int i = 0; i < ones; i++)
            cout << 1 << " ";
        cout << endl;
        return 0;
    }
    // If no ones are present.
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // searching for pair of integer having sum prime.
            if (check_prime[nums[i] + nums[j]] == 0){
                cout << 2 << endl;
                cout << nums[i] << " " << nums[j] << endl;
                return 0;
            }
        }
    }
// If only one element is present in the array.
    cout << -1 << endl;
    return 0;
}

Output

3
1 1 2

위 코드 설명

• 먼저 배열의 숫자를 확인합니다.

• 0보다 큰 경우 배열을 반복하고 1 nums[i] + 1을 제외한 각 요소가 소수인지 확인합니다. 그렇다면 전체 (1 + 1) 수를 하위 집합의 크기로 인쇄합니다. 그 숫자는 숫자가 모두 1입니다.

• 주어진 배열에 1만 포함되어 있으면 모든 쌍의 합은 2(소수)가 되므로 모두 인쇄하세요.

• 아무도 없으면 배열의 각 쌍의 합이 소수인지 확인하세요.

• Else 인쇄 -1.

결론

이 튜토리얼에서는 각 쌍의 합이 소수인 주어진 배열에서 가장 큰 부분 집합을 찾아야 하는 문제에 대해 논의했습니다. 우리는 에라토스테네스의 체(Sieve of Eratosthenes)의 도움으로 이 문제를 해결하고 배열의 숫자를 확인하는 방법을 논의했습니다. 또한 이 문제를 해결하기 위해 C, Java, Python 등과 같은 프로그래밍 언어를 사용하여 구현할 수 있는 C++ 프로그램에 대해서도 논의했습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 C++ 각 요소 쌍의 합이 소수인 최대 하위 집합의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!