package com.patience.interview.huawei;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class PrimeCouple {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.valueOf(br.readLine());
String [] lines = br.readLine().split("\\s");
List<Integer> odds = new ArrayList<>(8);
List<Integer> evens = new ArrayList<>(8);
for(String i : lines){
int item = Integer.valueOf(i);
if(item % 2 == 1){
odds.add(item);
}
if(item % 2 == 0){
evens.add(item);
}
}
int count = 0;
int [] matchEvens = new int[evens.size()];
for(int odd : odds){
boolean [] v = new boolean[evens.size()];
if(find(odd,matchEvens,evens,v)){
count++;
}
}
System.out.println(count);
}
static boolean find(int odd,int[] matchEvens,List<Integer> evens,boolean[] v){
for (int i = 0; i < evens.size(); i++){
boolean prime = isPrime(odd + evens.get(i));
if(prime && !v[i]){
v[i] = true;
if(matchEvens[i] == 0 || find(matchEvens[i],matchEvens,evens,v)){
matchEvens[i] = odd;
return true;
}
}
}
return false;
}
private static boolean isPrime(int n) {
if(n == 1) return false;
for (int i = 2;i <= (int)Math.sqrt(n); i++){
if(n % i == 0)
return false;
}
return true;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)