資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究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'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
以上程式碼的解釋
首先，我們檢查陣列中 1 的數量。
如果它大於 0，則遍歷陣列並檢查除 1 之外的每個元素，是否 nums[i] + 1 是素數；如果是，則列印 (1 的數量 + 1) 的總數作為子集的大小，以及所有 1 和該數字。
如果給定陣列只包含 1，則列印所有 1，因為所有對的和將是 2（素數）。
如果沒有 1，則檢查陣列中每對元素的和是否為素數。
否則，列印 -1。
結論
在本教程中，我們討論了一個問題，我們需要從給定的陣列中找到最大的子集，其中每對元素的和都是素數。我們討論了一種利用埃拉託斯特尼篩法解決此問題的方法，並檢查陣列中 1 的數量。我們還討論了此問題的 C++ 程式，我們可以使用 C、Java、Python 等程式語言來實現。希望本教程對您有所幫助。
更新於: 2021-11-25
117 次檢視
廣告