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 の 3 つの数値を使用します。そのうちの 2 つは奇数または偶数である必要があります。次に、このサブセットに素数と和のペアが含まれているかどうかを確認します。これは、次の場合に可能である可能性があります。素数。

• または、サブセットに数値が 2 つだけ含まれている場合、それらの合計は素数になります。

• 例

   #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'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 を除く各要素が nums[i] であるかどうかを確認します。1 は素数です。素数である場合は、(ones 1) の合計数を出力します。 ) サブとして セットのサイズとその数値のすべて 1。

• 指定された配列に 1 だけが含まれている場合は、すべてのペアの合計が 2 (素数) になるため、それらをすべて出力します。

• 誰も存在しない場合は、配列内の各ペアの合計が素数であることを確認します。

• それ以外の場合は -1 を出力します。

• 結論

このチュートリアルでは、各ペアの合計が素数となる、指定された配列から最大のサブセットを見つける必要がある問題について説明しました。私たちは、エラトステネスのふるいを利用して配列内の数値をチェックしてこの問題を解決する方法について話し合いました。この問題を解決するための C プログラムについても説明しました。C、Java、Python などのプログラミング言語を使用して実装できます。このチュートリアルがお役に立てば幸いです。

以上がC++ 要素の各ペアの合計が素数となる最大サブセットの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。