题目描述:
若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”,如2和5、6和13,它们能应用于通信加密。现在密码学会请你设计一个程序,从已有的N(N为偶数)个正整数中挑选出若干对组成“素数伴侣”,挑选方案多种多样,例如有4个正整数:2,5,6,13,如果将5和6分为一组中只能得到一组“素数伴侣”,而将2和5、6和13编组将得到两组“素数伴侣”,能组成“素数伴侣”最多的方案称为“最佳方案”,当然密码学会希望你寻找出“最佳方案”。
输入:
有一个正偶数N(N≤100),表示待挑选的自然数的个数。后面给出具体的数字,范围为[2,30000]。
输出:
输出一个整数K,表示你求得的“最佳方案”组成“素数伴侣”的对数。
Java实现:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
ArrayList<Integer> ji =new ArrayList<>();//存放奇数
ArrayList<Integer> ou =new ArrayList<>();//存放偶数
for(int i=0;i<n;i++){
int x=sc.nextInt();
if(x%2==0)
ou.add(x);
else
ji.add(x);
}
int[] used =new int[ou.size()];
int[] oushu =new int[ou.size()];
int sum=0;
for(int i=0;i<ji.size();i++){
//对每个奇数依次在所有偶数中
Arrays.fill(used, 0);
if(find(ji.get(i),ou,used,oushu)) sum++;
}
System.out.println(sum);
}
}
private static boolean find(Integer x, ArrayList<Integer> ou, int[] used, int[] oushu) {
for (int j=0;j<ou.size();j++){//扫描每个偶数
if (isprim(x+ou.get(j)) && used[j]==0)
{
used[j]=1;
if (oushu[j]==0 || find(oushu[j],ou,used,oushu)) {
oushu[j]=x;//索引为j的偶数对应的奇数
return true;
}
}
}
return false;
}
private static boolean isprim(Integer x) {
int sum=0;
for(int i=2;i<=Math.pow(x, 0.5);i++){
if(x%i==0) return false;
}
return true;
}
}
知识点:
- 判断一个数是否为素数,就看它能否被比它的开平方的数小的所有数整除
- 在所有素数中,除了2之外都是奇数,只有奇数+偶数才能为奇数,因此将输入的数分为奇数和偶数两部分
- TODO:匈牙利算法:二分图匹配
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)