주어진 배열에서 모든 쌍의 합이 소수인 가장 큰 부분집합을 찾는 것. 최대 요소가 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
위 코드 설명
-
먼저 배열의 개수를 확인합니다.
-
0보다 크면 배열을 탐색하고 nums[i] + 1이 소수인지 여부를 1이 아닌 각 요소를 확인합니다. 그렇다면 (일 + 1)의 총 수를 부분 집합의 크기로 인쇄하고 숫자가 있는 모든 것을 인쇄하십시오.
-
주어진 배열에 1만 포함되어 있으면 모든 쌍의 합이 2(소수)가 되므로 모든 1을 인쇄하십시오.
-
아무도 없으면 배열의 모든 쌍을 합 소수로 확인하십시오.
-
그렇지 않으면 -1을 인쇄합니다.
결론
이 튜토리얼에서 우리는 주어진 배열에서 각 쌍의 합이 소수인 가장 큰 부분집합을 찾아야 하는 문제에 대해 논의했습니다. 우리는 에라토스테네스의 체를 사용하여 이 문제를 해결하고 배열의 개수를 확인하는 접근 방식에 대해 논의했습니다. 우리는 또한 C, Java, Python 등과 같은 프로그래밍 언어로 할 수 있는 이 문제에 대한 C++ 프로그램에 대해 논의했습니다. 이 튜토리얼이 도움이 되기를 바랍니다.