首页 > 试题广场 >

素数伴侣

[编程题]素数伴侣

热度指数：198773 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 定义两个正整数 $a$ 和 $b$ 是“素数伴侣”，当且仅当 $a + b$ 是一个素数。
$\hspace{15pt}$ 现在，密码学会邀请你设计一个程序，从给定的 $n$ 个正整数 $\left\{a_1, a_2, \dots, a_n\right\}$ 中，挑选出最多的“素数伴侣”，你只需要输出挑选出的“素数伴侣”对数。保证 $n$ 为偶数，一个数字只能使用一次。

输入描述:

第一行输入一个正偶数  代表数字个数。
第二行输入  个正整数  代表给定的数字。

输出描述:

输出一个整数，代表最多可以挑选出的“素数伴侣”的数量。

示例1

输入

4
2 5 6 13

输出

说明

在这个样例中， 和  可以组成一对素数伴侣， 和  也可以组成一对素数伴侣。因此，最多可以挑选出  对素数伴侣。

示例2

输入

4
1 2 2 2

输出

说明

在这个样例中， 只能使用一次，与任意一个  组合均是“素数伴侣”。

示例3

输入

2
3 6

输出

算法知识视频讲解

推荐

toraoh

OK，我们把这个话题终结一下。

所有想着动态规划的，你们放弃吧，不是这么玩的。

考虑使用图论的方法来给这个题建模。

100个数看成100个点，如果这两个数加起来的和是素数，给这两个数中间连一条边。

之后，我们要选择尽可能多的边，要求这些边不共享端点。

——这个东西呢，叫做一般无向图的最大匹配。

但是，一般无向图的最大匹配，这个算法的难度，有点，大……

这个问题，合适的算法叫，带花树开花算法。

具体参见：http://blog.csdn.net/yihuikang/article/details/10460997

和 http://fanhq666.blog.163.com/blog/static/8194342620120304463580/

现场推完这么多，写一个正确的，有点不科学……

我们考虑再分析一下这个题

注意到，每个数的取值范围是[2,30000]

素数，除了2是偶数，其他是奇数——而现在不可能出现2了，所以我们只考虑奇数的素数

2个数的和是奇数，有什么情况呢？

只有奇数+偶数

所以，我们把这些数分成2堆——奇数和偶数，然后在他们中间，和是素数的，连上一条边，然后做匹配。

——肯定有人会说，你这个和前面的建图有什么本质不同的地方吗？

——是没有，但是我们说明了得到的图一定是二分图，这是有意义的。

因为对二分图的最大匹配，有一个简单很多的算法，匈牙利算法。

我们先说明一下，什么是二分图。

二分图就是，你可以把图上的点分成2堆，每堆之内的点不会有边，2堆之间，才可能连边。换句话说，一条边，必定连2个来自不同堆的点。

现在，对每条边，一定连一个奇数，一个偶数，点能按奇数和偶数分成两部分，刚好就是二分图嘛！

有关二分图匹配的匈牙利算法，具体请自行搜索，这里扯一下我个人对这个算法的理解。

外层，暴力考虑左边每个点

对枚举的每个左边的点，要找右边一个点来匹配。

那就是对左边的点，我们看他连出去的边，或者说，能连到的右边的点

有2种情况：

1、右边的点没人匹配——我直接贪心匹配上去

2、右边的点有人匹配——考虑把目前与这个右边的点 x 匹配的左边的点 pre[x]，重新匹配一个其他的点，如果成功了，那pre[x]原来匹配的点x就释放开了，我可以直接占领上去。

最后统计匹配成功多少个左边的点就行了。

匈牙利算法真的还是很短的，比你写一个红黑树轻松多了：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> G[105];

bool flag[105];
int pre[105];

bool dfs(int k){
    int x;
    for(int i=0;i<G[k].size();i++){
        x=G[k][i];
        if (flag[x]) continue;
        flag[x]=true;
        if((pre[x]==0)||dfs(pre[x])){
            pre[x]=k;
            return true;
        }
    }
    return false;
}

bool isprime[80000];
int nums[105];

int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    int n;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=1;i<=n;++i){
            for(int j=i+1;j<=n;++j){
                if(isprime[nums[i]+nums[j]]){
                    (nums[i]&1)?G[i].push_back(j):G[j].push_back(i);
                }
            }
        }

        memset(pre,0,sizeof(pre));
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(flag,false,sizeof(flag));
            if (dfs(i)) ans++;
        }
        printf("%d\n",ans);
        
        for(int i=1;i<=n;++i){
            G[i].clear();
        }
    }
    return 0;
}

（当然，你用网络流做二分图最大匹配，没人拦你。）

最后，给好学的人：

一般图匹配（牛刀）来做这个题（杀鸡）的代码：

带花树开花的模板 CopyRight Claris（http://www.lydsy.com/JudgeOnline/userinfo.php?user=Claris）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=510;
int n,m,x,y;vector<int>g[N];
namespace Blossom{
    int mate[N],n,ret,nxt[N],f[N],mark[N],vis[N];queue<int>Q;
    int F(int x){return x==f[x]?x:f[x]=F(f[x]);}
    void merge(int a, int b){f[F(a)]=F(b);}
    int lca(int x, int y){
        static int t=0;t++;
        for(;;swap(x,y)) if(~x){
            if(vis[x=F(x)]==t) return x;vis[x]=t;
            x=mate[x]!=-1?nxt[mate[x]]:-1;
        }
    }
    void group(int a, int p){
        for(int b,c;a!=p;merge(a,b),merge(b,c),a=c){
            b=mate[a],c=nxt[b];
            if(F(c)!=p)nxt[c]=b;
            if(mark[b]==2)mark[b]=1,Q.push(b);
            if(mark[c]==2)mark[c]=1,Q.push(c);
        }
    }
    void aug(int s, const vector<int>G[]){
        for(int i=0;i<n;++i)nxt[i]=vis[i]=-1,f[i]=i,mark[i]=0;
        while(!Q.empty())Q.pop();Q.push(s);mark[s]=1;
        while(mate[s]==-1&&!Q.empty()){
        int x=Q.front();Q.pop();
        for(int i=0,y;i<(int)G[x].size();++i){
                if((y=G[x][i])!=mate[x]&&F(x)!=F(y)&&mark[y]!=2){
                    if(mark[y]==1){
                        int p=lca(x,y);
                        if(F(x)!=p)nxt[x]=y;
                        if(F(y)!=p)nxt[y]=x;
                        group(x,p),group(y,p);
                    }else if(mate[y]==-1){
                        nxt[y]=x;
                        for(int j=y,k,l;~j;j=l)k=nxt[j],l=mate[k],mate[j]=k,mate[k]=j;
                        break;
                    }else nxt[y]=x,Q.push(mate[y]),mark[mate[y]]=1,mark[y]=2;
                }
            }
        }
    }
    int solve(int _n, const vector<int>G[]){
        n=_n;memset(mate, -1, sizeof mate);
        for(int i=0;i<n;++i) if(mate[i]==-1)aug(i,G);
        for(int i=ret=0;i<n;++i)ret+=mate[i]>i;
        printf("%d\n",ret);
        //for(int i=0;i<n;i++)printf("%d %d\n",i+1,mate[i]+1);
        return ret;
    }
}
bool isprime[80000];
int nums[105];
int main(){
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for(int i=4;i<80000;i+=2)isprime[i]=false;
    for(int i=3;i*i<80000;i+=2)
        if(isprime[i]){
            for(int j=i*i;j<80000;j+=2*i) isprime[j]=false;
        }
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
            scanf("%d",&nums[i]);
        }
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                if(isprime[nums[i]+nums[j]]){
                    g[i].push_back(j);
                    g[j].push_back(i);
                }
            }
        }
        Blossom::solve(n,g);
        for(int i=0;i<n;++i){
            g[i].clear();
        }
    }
}

最后吐槽：华为这题出得都快和微软一个尿性了，二分图匹配和DAG上求支配者树，这个都不怎么好想出来的，硬生生想出来的，这个值得膜一膜，但是做出这个题的人，更多情况是，学过这个东西吧？

（你看这题的讨论区，多少人跳进了dp的大坑爬不出来？）

于是这是笔试题/面试题从一个极端走向另一个极端（从语言和库知多少，走向算法知识知多少）？

编辑于 2016-09-10 13:03:39 回复(48)

JavaScript Node

十一尾

void async function () {

// Write your code here

let tokens = [] //创建初始接收数组

while(line = await readline()){

tokens = line.split(' ');

let a = parseInt(tokens[0]);

let b = parseInt(tokens[1]);

}

let n = tokens.length //总数目

const pre = new Array(n) //用于记录与某个数匹配的另一个数的集

const vis = new Array(n) //记录某个数是否已经被使用

const is_prime = (x) => {//判断x是否为素数

if(x<=1) return false

for(let i=2;i*i<=x;i++){

if(x%i == 0)

return false

}

return true

}

const find = (a) => {//查找素数伴侣

for(let u of g[a]){

if(vis[u]) continue //如果已经被访问了,skip

vis[u] = true //未访问则进行匹配标记

if(pre[u]==-1||find(pre[u])){//==-1则未匹配，后者说明是还有其他点可以匹配

pre[u] = a//如果满足则设置u与a为匹配项

return true

}

return false

}

const hungry = (n) => {//计算匹配数

let ans = 0

pre.fill(-1)

for(let i = 0;i<n;i++){//对每个点进行匹配查询

vis.fill(false)

if(find(i)){

ans++

}

return ans

}

//程序主体

const g = [] //用于建边

for(let i=0;i<n;i++){

g.push([])

}

// console.log(g)

for(let i=0;i<n;i++){

for(let j=i+1;j<n;j++){

if(is_prime(parseInt(tokens[i])+parseInt(tokens[j]))){

// console.log(tokens[i]+" "+tokens[j])

// console.log(i+" "+j)

g[i].push(j)

g[j].push(i)

}

// console.log(g[i])

}

// console.log(g)

console.log(hungry(n)/2)

}()

发表于 2025-06-26 22:28:49 回复(1)

JavaScript Node

soulor.魂

    while ((line = await readline())) {
        let n = Number(line);
        let odd = [];
        let even = [];
        // 把数据分成奇数和偶数，因为奇数+偶数才能得出奇数，所有素数除了2以外都是奇数
        (await readline()).split(" ").forEach((v) => {
            v = Number(v);
            if (v % 2 === 0) {
                even.push(v);
            } else {
                odd.push(v);
            }
        });

        if (odd.length == 0 || even.length == 0) {
            console.log(0);
            return;
        }
        // 遍历并找到所有素数伴侣
        const map = [];
        for (let i = 0; i < odd.length; i++) {
            map[i] = new Array(even.length);
            for (let j = 0; j < even.length; j++) {
                map[i][j] = isPrime(odd[i] + even[j]);
            }
        }

        let count = 0;
        let usedEven = []; // 存放每次遍历里面的偶数下标，防止无限递归
        let matchArr = []; // matchArr[j]存放偶数j对应的奇数下标i
        for (let i = 0; i < odd.length; i++) {
            if (isMach(i)) {
                count++;
                usedEven = [];
            }
        }

        console.log(count);

        function isMach(i) {
            for (let j = 0; j < even.length; j++) {
                // i、j对应的奇偶数的话如果不是素数或者当前偶数下标在这次isMach递归中已经使用过则直接跳过当前循环
                if (!map[i][j] || usedEven[j]) continue;
                usedEven[j] = true;
                // 如果j没有匹配过，或者原来跟j匹配的奇数matchArr[j]能找到其他匹配
                if (matchArr[j] === undefined || isMach(matchArr[j])) {
                    matchArr[j] = i;
                    return true;
                }
            }
            return false;
        }
        function isPrime(n) {
            let res = true;
            for (let i = 2; i * i <= n; i++) {
                if (n % i === 0) {
                    res = false;
                }
            }
            return res;
        }
    }

发表于 2023-05-22 12:05:44 回复(0)

JavaScript Node

响亮亮xpp

const rl = require("readline").createInterface({ input: process.stdin });

var iter = rl[Symbol.asyncIterator]();

const readline = async () => (await iter.next()).value;

void (async function () {

// Write your code here

let arr = [];

while ((line = await readline())) {

arr.push(line);

}

let numArr = arr[1].split(" ");

let doubleNum = 0;

let usedArr = [];

for (let i = 0; i < numArr.length; i++) {

for (let j = i + 1; j < numArr.length; j++) {

let plusRes = Number(numArr[i]) + Number(numArr[j]);

if (

usedArr.includes(Number(numArr[i])) ||

usedArr.includes(Number(numArr[j]))

)

) {

if (isPrime(plusRes)) {

usedArr.push(Number(numArr[i]), Number(numArr[j]));

doubleNum += 1;

}

console.log(doubleNum);

// 判断和是否为质数

function isPrime(num) {

for (let i = 2; i < num; i++) {

if (num % i === 0) {

return false;

}

return true;

}

})();

发表于 2023-03-30 16:46:50 回复(1)

提交观点

问题信息

查找排序

难度：

3条回答 4686收藏 62326浏览

通过挑战的用户

查看代码

Deersta...

2023-03-10 17:24:29
amongo

2023-02-05 00:00:38
于铭扬

2022-09-17 18:31:04
散装散人

2022-09-16 15:28:02
牛客50821...

2022-09-16 15:04:19

素数伴侣

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题