C++ 最大子集,其中每对元素的和为质数

2023年 8月 27日 58.4k 0

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
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 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

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论