首頁 >後端開發 >C++ >C++ 最大子集,其中每對元素的和為質數

C++ 最大子集,其中每對元素的和為質數

WBOY
WBOY轉載
2023-08-26 08:05:171254瀏覽

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應該是質數。

  • 或如果子集只包含兩個數,它們的和是質數。

範例

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

輸出

3
1 1 2

上述程式碼說明

  • 首先我們檢查陣列中的個數。

  • 如果大於0,則遍歷數組,檢查除1以外的每個元素是否為子集的大小以及具有該數字的所有1。
  • 如果給定陣列只包含 1,列印所有的,因為所有對的總和將為 2(質數)。

  • 如果沒有人在場,則檢查陣列中的每一對的總和為質數。

  • Else print -1。

結論

在本教程中,我們討論了一個問題,其中我們需要從給定數組中找到最大的子集,其中每對的總和為素數。我們討論了一種借助埃拉托斯特尼篩法來解決這個問題的方法,並檢查數組中的個數。我們也討論了解決此問題的 C 程序,我們可以使用 C、Java、Python 等程式語言來實作。我們希望本教學對您有所幫助。

以上是C++ 最大子集,其中每對元素的和為質數的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除