從給定數組中找到最大的子集，其中每對元素的和是一個質數。假設最大元素是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應該是質數。
或如果子集只包含兩個數，它們的和是質數。
#includeusing 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，列印所有的，因為所有對的總和將為 2（質數）。
如果沒有人在場，則檢查陣列中的每一對的總和為質數。
Else print -1。
在本教程中，我們討論了一個問題，其中我們需要從給定數組中找到最大的子集，其中每對的總和為素數。我們討論了一種借助埃拉托斯特尼篩法來解決這個問題的方法，並檢查數組中的個數。我們也討論了解決此問題的 C 程序，我們可以使用 C、Java、Python 等程式語言來實作。我們希望本教學對您有所幫助。
以上是C++ 最大子集，其中每對元素的和為質數的詳細內容。更多資訊請關注PHP中文網其他相關文章！
