HJ28. 素数伴侣
描述
题目描述
若两个正整数的和为素数，则这两个正整数称之为“素数伴侣”，如2和5、6和13，它们能应用于通信加密。现在密码学会请你设计一个程序，从已有的 N （ N 为偶数）个正整数中挑选出若干对组成“素数伴侣”，挑选方案多种多样，例如有4个正整数：2，5，6，13，如果将5和6分为一组中只能得到一组“素数伴侣”，而将2和5、6和13编组将得到两组“素数伴侣”，能组成“素数伴侣”最多的方案称为“最佳方案”，当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数 n ，表示待挑选的自然数的个数。后面给出 n 个具体的数字。
输出:
输出一个整数 K ，表示你求得的“最佳方案”组成“素数伴侣”的对数。
输入描述
输入说明
1 输入一个正偶数 n
2 输入 n 个整数
输出描述
求得的“最佳方案”组成“素数伴侣”的对数。
示例1
输入:
4 2 5 6 13
输出:
2
示例2
输入:
2 3 6
输出:
0
C 解法, 执行用时: 2ms, 内存消耗: 296KB, 提交时间: 2021-09-26
#include <stdio.h>
#include <string.h>
#include <math.h>
char used[88], match[88][88];
int even[88], idx_e, odd[88], idx_o, cp[88], cnt, *small, idx_s, *big, idx_b;
int IsPrime(int num)
{
int i=2, j=sqrt(num);
for( ; i<=j; i++){
if(num%i) continue;
return 0;
}
return 1;
}
int DG(int n)
{
int i;
for(i=0; i<idx_b; i++){
if( match[n][i] && !used[i] ){
used[i] = 1;
if( cp[i] == -1 ){ cp[i] = n; cnt++; return 1; }
if( DG(cp[i]) ){ cp[i] = n; return 1; }
}
}
return 0;
}
int main(void)
{
int i, j, tmp, num;
for( ; scanf("%d", &num)!=EOF; ){
if(num & 0x1) return -1008611;
idx_o = idx_e = 0;
for(i=0; i<num; i++){
scanf("%d", &tmp);
if(tmp&1){ odd[idx_o++] = tmp; continue; }
even[idx_e++] = tmp;
}
if(idx_o>idx_e){ small=even; idx_s=idx_e; big=odd; idx_b=idx_o; }
else{ small=odd; idx_s=idx_o; big=even; idx_b=idx_e; }
for(i=0; i<idx_s; i++){
tmp = small[i];
for(j=0; j<idx_b; j++){
if( IsPrime( tmp+big[j] ) ){ match[i][j] = 1; continue; }
match[i][j] = 0;
}
}
memset(cp, -1, idx_b*sizeof(int));
for(i=cnt=0; i<idx_s; i++){
memset(used, 0, idx_b*sizeof(char));
DG(i);
}
printf("%d\n", cnt);
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 316KB, 提交时间: 2021-12-06
#include <stdio.h>
#include <string.h>
#include <math.h>
char used[88], match[88][88];
int even[88], idx_e, odd[88], idx_o, cp[88], cnt, *small, idx_s, *big, idx_b;
int IsPrime(int num)
{
int i=2, j=sqrt(num);
for( ; i<=j; i++){
if(num%i)
continue;
return 0;
}
return 1;
}
int DG(int n)
{
int i;
for(i=0; i<idx_b; i++){
if( match[n][i] && used[i]==0 ){
used[i] = 1;
if(cp[i] == -1){
cp[i] = n;
cnt++;
return 1;
}
if(DG(cp[i])){
cp[i] = n;
return 1;
}
}
}
return 0;
}
int main(void)
{
int i, j, tmp, num;
for( ; scanf("%d", &num)!=EOF; ){
if(num & 1)
return -1;
idx_o = idx_e = 0;
for(i=0; i<num; i++){
scanf("%d", &tmp);
if(tmp&1)
odd[idx_o++] = tmp;
else
even[idx_e++] = tmp;
}
if(idx_o>idx_e){
small=even;
idx_s=idx_e;
big=odd;
idx_b=idx_o;
}
else{
small=odd;
idx_s=idx_o;
big=even;
idx_b=idx_e;
}
for(i=0; i<idx_s; i++){
tmp = small[i];
for(j=0; j<idx_b; j++){
if(IsPrime(tmp+big[j])){
match[i][j] = 1;
continue;
}
match[i][j] = 0;
}
}
memset(cp, -1, idx_b*sizeof(int));
for(i=cnt=0; i<idx_s; i++){
memset(used, 0, idx_b*sizeof(char));
DG(i);
}
printf("%d\n", cnt);
}
return 0;
}