Để tìm tập con lớn nhất từ mảng đã cho, trong đó tổng của mọi cặp là một số nguyên tố. Ví dụ, giả sử phần tử tối đa là 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. Phương pháp tiếp cận để tìm giải pháp
Để tìm xem cặp số có phải là số nguyên tố hay không, trước hết chúng ta cần kiểm tra xem tổng của nó là lẻ hay chẵn vì các số chẵn không phải là số nguyên tố ngoại trừ 2. Và tổng của hai số có thể là chẵn nếu cả hai số đó đều là số lẻ hoặc số chẵn.
Trong bài toán này, chúng ta sẽ lấy ba số, x, y và z, trong đó hai số bất kỳ phải là chẵn hoặc lẻ. Sau đó, chúng tôi sẽ kiểm tra tập hợp con này để tìm các cặp tổng nguyên tố và điều này có thể thực hiện được nếu,
-
Tập hợp con chứa một số số của 1 và một số số khác trong đó NUM + 1 phải là số nguyên tố.
-
Hoặc nếu tập hợp con chỉ chứa hai số có tổng là số nguyên tố.
Ví dụ
#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;
} Đầu ra
3 1 1 2
Giải thích về Quy tắc trên
-
Đầu tiên, chúng tôi đang kiểm tra số lượng cái trong mảng.
-
Nếu nó lớn hơn 0, thì hãy duyệt qua mảng và kiểm tra từng phần tử khác một phần tử xem nums [i] + 1 có phải là số nguyên tố hay không; nếu có, sau đó in tổng số (cái + 1) làm kích thước của tập hợp con và tất cả những cái có số.
-
Nếu mảng đã cho chỉ chứa các dãy số, hãy in tất cả các dãy số vì tổng của tất cả các cặp sẽ là 2 (số nguyên tố).
-
Nếu không có ai, hãy kiểm tra mọi cặp trong mảng có tổng nguyên tố không.
-
In khác -1.
Kết luận
Trong hướng dẫn này, chúng ta đã thảo luận về một vấn đề trong đó chúng ta cần tìm tập con lớn nhất từ mảng đã cho, trong đó tổng của mỗi cặp là số nguyên tố. Chúng tôi đã thảo luận về một cách tiếp cận để giải quyết vấn đề này với sự trợ giúp của sàng Eratosthenes và để kiểm tra số lượng đơn vị trong mảng. Chúng tôi cũng đã thảo luận về chương trình C ++ cho vấn đề này mà chúng tôi có thể làm với các ngôn ngữ lập trình như C, Java, Python, v.v. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.