题解 | #素数伴侣#
素数伴侣
https://www.nowcoder.com/practice/b9eae162e02f4f928eac37d7699b352e
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int i = scanner.nextInt(); int[] ints = new int[i]; ArrayList<Integer> odd = new ArrayList<>(); ArrayList<Integer> even = new ArrayList<>(); for (int j = 0; j <i; j++) { ints[j]=scanner.nextInt(); if (ints[j]%2==0){ even.add(ints[j]); }else { odd.add(ints[j]); } } int[] match = new int[even.size()];//下标对应已经匹配的偶数的下标,值对应这个偶数的伴侣 int count=0; for (int j = 0; j < odd.size(); j++) { boolean[] ifpped= new boolean[even.size()];//标记对应该奇数是否匹配过每一个偶数 if(success(odd.get(j),even,match,ifpped)){ count++; } } System.out.println(count); } public static boolean success(int odd,ArrayList<Integer> even,int[] match,boolean[] ifpped){ for (int i = 0; i < even.size(); i++) { if (isPrime(odd+even.get(i))&&ifpped[i]==false){ ifpped[i]=true; if(match[i]==0||success(match[i],even, match,ifpped)){//如果当前偶数没有伴侣或偶数有的奇数伴侣可以找到其他偶数伴侣 match[i]=odd; return true; } } } return false; } public static boolean isPrime(int n) { if (n <= 3) { return n > 1; } //判断一个数能否被小于sqrt(n)的数整除 int sqrt = (int)Math.sqrt(n); for (int i = 2; i <= sqrt; i++) { if(n % i == 0) { return false; } } return true; } }