输入:
有一个正偶数N（N≤100），表示待挑选的自然数的个数。后面给出具体的数字，范围为[2,30000]。
输出:
输出一个整数K，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入: 输入说明
1 输入一个正偶数n
2 输入n个整数
输出:求得的“最佳方案”组成“素数伴侣”的对数。
样例输入:
4
2 5 6 13
样例输出:
2
#include <iostream>
#include <cmath>
using namespace std;
#define N 100
#define M 30000
int isPrime( int nNum );
int getBestSol( int *nNums, char *bUsed, int nLen, int nDoubles = 0 );
char bPrimes[M + 1];
int main( void )
{
int n;
int nNums[N];
char bUsed[N];
bPrimes[0] = 0;
for( int i = 1; i <= M; ++i ){
bPrimes[i] = isPrime( i );
}
cin >> n;
for( int i = 0; i < n; ++i ){
cin >> nNums[i];
bUsed[i] = 0;
}
// int nDoubles = 0;
cout << getBestSol( nNums, bUsed, n ) << endl;
return 0;
}
int isPrime( int nNum )
{
if( nNum == 1 )
return 0;
if( nNum == 2 )
return 1;
int nSqrt = sqrt( static_cast<double>( nNum ) );
for( int i = 2; i <= nSqrt; ++i )
if( nNum % i == 0 )
return 0;
return 1;
}
int getBestSol( int *nNums, char *bUsed, int nLen, int nDoubles )
{
int i = 0;
while( bUsed[i] && i < nLen )
++i;
if( i == nLen )
return nDoubles;
bUsed[i] = 1;
int maxDoubles = 0, nDoublesOut = 0;
for( int j = i + 1; j < nLen; ++j ){
if( bUsed[j] == 0 ){
bUsed[j] = 1;
int nDoublesIn = ( bPrimes[nNums[i] + nNums[j]] ? ( nDoubles + 1 ) : nDoubles );
nDoublesOut = getBestSol( nNums, bUsed, nLen, nDoublesIn );
bUsed[j] = 0;
if( maxDoubles < nDoublesOut )
maxDoubles = nDoublesOut;
if( maxDoubles == nLen / 2 )
return maxDoubles;
}
}
bUsed[i] = 0;
return maxDoubles;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
