华为OJ——素数伴侣

本文主要是介绍华为OJ——素数伴侣，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

素数伴侣

题目描述

题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的N（N为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。

输入:

有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。

输出:

输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。

输入描述:

输入说明
1 输入一个正偶数n
2 输入n个整数

输出描述:

求得的“最佳方案”组成“素数伴侣”的对数。

输入例子:

4

2 5 6 13

输出例子:

2

解答代码：

#include<iostream>
#include<fstream>
#include <vector>
#include <cmath>
#define N 102
using namespace std;//判断素数
bool isPrime(int n)
{int i;if (n <= 1)return false;for(i=2; i<n; i++){if(n%i==0)break;}if(i==n)return true;return false;
}int PrimePairs(int array[],int length)
{int dp[N];int i,j;int count=0;//初始化dp数组for(i=0; i<N; i++)dp[i]=0;for(i=length-2; i>-1; i--){for(j=length-1; j>i; j--){//如果array[i]+array[j]的和构成素数if(isPrime(array[i]+array[j])){count=dp[i+1]-dp[j-1]+dp[j+1]+1;}else{count=dp[i+1];}if(count>dp[i])dp[i]=count;}}return dp[0];
}int main()
{int i,length;int array[N];//freopen("input.txt", "r", stdin);while (cin >> length){//输入数据for(i=0; i<length; i++)cin>>array[i];//处理cout<<PrimePairs(array,length)<<endl;}return 0;
}

这篇关于华为OJ——素数伴侣的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---