素数伴侣

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    private static List<Integer> odds = new ArrayList<>();//存储奇数
    private static List<Integer> evens = new ArrayList<>();//存储偶数
    private static List<List<Integer>> adj = new
    ArrayList<>();//邻接表，存储每个奇数能配对的偶数索引
    private static boolean[] used;//标记偶数是否在当前DFS中已被访问
    private static int[]
    match;//记录每个偶数匹配的奇数索引(-1表示未匹配)
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();//输入数字个数
        if (n % 2 != 0) return;
        // 1. 接收输入的数字,并分别放入奇数列表和偶数列表中
        for (int i = 0; i < n;
                i++) { //接收输入的数字,并分别放入奇数列表和偶数列表中
            int temp = in.nextInt();
            if (temp == 0) continue;
            if (temp % 2 == 0) {
                evens.add(temp);
            } else {
                odds.add(temp);
            }
        }
        // 2. 构建邻接表：预处理每个奇数可以和哪些偶数组成素数对
        for (int i = 0; i < odds.size(); i++) {
            adj.add(new ArrayList<>());
            for (int j = 0; j < evens.size(); j++) {
                if (isPrime(odds.get(i) + evens.get(j))) {
                    adj.get(i).add(
                        j);//记录奇数i可以和偶数j配对，记录在各自列表的索引，方便后续取数字
                }
            }
        }
        // 3. 初始化匹配数组
        used = new boolean[evens.size()];
        match = new int[evens.size()];
        Arrays.fill(match,
                    -1); // 初始时所有偶数都未匹配，同样记录的是索引
        // 4. 对每个奇数，尝试寻找增广路径
        int count = 0;
        for (int i = 0; i < odds.size(); i++) {
            Arrays.fill(used, false); //每次DFS前重置访问标记
            if (dfs(i)) {
                count++;
            }
        }
        System.out.println(count);
    }
    private static boolean dfs(int u) {
        for (int v : adj.get(u)) {
            if (!used[v]) { //如果偶数v未被访问
                used[v] = true;//设置访问标记
                //如果偶数v未匹配，或v已匹配但能为其原匹配的奇数找到新配对
                if (match[v] == -1 ||
                        dfs(match[v])) { //递归调用 dfs(match[v])，尝试为该奇数寻找其他可用偶数
                    match[v] = u; // 更新v的匹配为u
                    return true;//找到增广路径
                }
            }
        }
        return  false;//未找到增广路径
    }
    //使用缓存来减少判断素数循环
    private  static Map<Integer, Boolean> map = new HashMap<>();
    //判断是否为素数
    private static boolean isPrime(int n) {
        if (n == 2 ) return true;//2为素数
        //偶数、1、负数不可能为素数
        if (n <= 1 || n % 2 == 0) return  false;
        if (map.containsKey(
                    n)) { //如果这个数字在缓存中已经存在，直接返回
            return map.get(n);
        }
        //从3开始除，知道n的开方，如果能除尽，则是非素数
        for (int i = 3; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                map.put(n, false);
                return false;
            }
        }
        //全部判断完成后没有除数的，为素数
        map.put(n, true);
        return true;
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static boolean[][] map = null; //横奇竖偶 ， 两者之和是否为素数
    static int[] match = null; //偶数暂时匹配的奇数
    static int odd=0; //数据数量
    static int even = 0; //数据数量

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt(); //数量
        
        int[] even_datas = new int[num];  //存储偶数
        int[] odd_datas = new int[num];  //存储奇数
        for (int i = 0; i < num; i++) {
            int data = scanner.nextInt();
            if(data%2!=0) {
                odd_datas[odd++] = data;
            }else {
                even_datas[even++]=data;
            }
        }

        map = new boolean[odd][even];
        match = new int[even];
        for (int i = 0; i < even; i++) { //计算是否为素数
            match[i]=-1;
            for (int j = 0; j < odd; j++) {
                map[j][i] = isTrue(odd_datas[j],even_datas[i]);
            }
        }

        int count = 0;

        for (int i = 0; i < odd; i++) {
            boolean[] visited = new boolean[even];//是否被占 ,奇数去抢夺偶数，当前轮的标记
            if(find(i,visited)){
                count++;
            }
        }
        System.out.println(count);
    }

    public static boolean find(int odd,boolean[] visited){
        for (int i = 0; i < even; i++) { //找偶数
            if(map[odd][i]&&!visited[i]){
                visited[i]=true;  //当前标记，odd想找这个
                if(match[i]==-1||find(match[i],visited)){ //当前偶数没有被占据，能让则让
                    match[i]=odd; //偶数标记
                    return true; //能找到
                }
            }
        }
        return false;
    }

    public static boolean isTrue(int num1,int num2){
        int sum = num1+num2;
        if(sum<=3)
            return true;
        if(sum%2==0||sum%3==0)
            return false;
        for (int i = 6; i <= sum/2; i+=6) {
            if(sum%(i-1)==0)
                return false;
            if(sum%(i+1)==0)
                return false;
        }
        return true;
    }
}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            ArrayList<Integer> odds = new ArrayList<>();
            ArrayList<Integer> evens = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int num = sc.nextInt();
                if (num % 2 == 0) {
                    evens.add(num);
                } else {
                    odds.add(num);
                }
            }
            int[] matcheven = new int[evens.size()];
            int count = 0;
            for (Integer odd : odds) {
                if (find(odd, matcheven, evens, new boolean[evens.size()])) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    private static boolean find(int x, int[] matcheven, ArrayList<Integer> evens,
                                boolean[] v) {
        for (int i = 0; i < evens.size(); i++) {
            int even = evens.get(i);
            if (isPrime(x + even) && !v[i]) {
                v[i] = true;
                if (matcheven[i] == 0 || find(matcheven[i], matcheven, evens, v)) {
                    matcheven[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPrime(int x) {
        if (x <= 1 || (x > 2 && x % 2 == 0)) {
            return false;
        }
        for (int i = 3; i <= Math.sqrt(x); i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 我的素数伴侣 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            // 素数：两个数组合在一起还是素数的话，除了两个1之外，就只剩下一奇数一偶数了
            List<Integer> odds = new ArrayList<>();
            List<Integer> evens = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int temp = in.nextInt();
                // 奇数，后边先打印一下，确认这里没问题
                if ((temp & 1) == 1) {
                    odds.add(temp);
                } else {
                    evens.add(temp);
                }
            }
            // 偶数的匹配情况，下边数组的索引代表第几个偶数被谁匹配了，如果对应的位置的值是 0 ，则没有匹配
            int[] evenMatched = new int[evens.size()];
            int result = 0;
            for (Integer odd : odds) {
                // 在接下来的一整个寻找过程中，要认为所有的偶数我都可以去挑选，因为【匈牙利算法的思想就是：先到先得，能让则让】
                // 所以其实每次都可以去抢别人的伴侣，如果被抢的人还能找到其他伴侣的话，则抢成功
                boolean[] used = new boolean[evens.size()];
                if (canMatch(used, odd, evens, evenMatched)) {
                    result++;
                }
            }
            System.out.println(result);
        }
    }

    private static boolean canMatch(boolean[] used, Integer odd, List<Integer> evens, int[] evenMatched) {
        for (int i = 0; i < evens.size(); i++) {
            Integer even = evens.get(i);
            // 如果当前的偶数与当前的奇数匹配，并且当前的偶数没被用掉
            if (isPrime(odd+ even) && !used[i]) {
                // 被用掉了，不管是被强抢了还是直接匹配成功了，当前的偶数都被用掉了
                used[i] = true;

                // evenMatched[i]==0：当前的偶数没有伴侣
                // canMatch(used, evenMatched[i], evens, evenMatched)：
                //      当前的偶数有伴侣，但是当前的偶数的伴侣，还能找到其他的伴侣，一直递归下去
                //      大体意思就是：你要么找一个单身的，要么如果去抢别人的伴侣的话，得确保被抢的单下来的一方还能找到另一个伴侣。可以递归去抢，但是得保证递归到最后的那个人也还是能再找到一个伴侣
                if (evenMatched[i]==0 || canMatch(used, evenMatched[i], evens, evenMatched)) {
                    evenMatched[i] = odd;
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPrime(int num) {
        if (num==1) {
            return false;
        }
        if (num==2) {
            return true;
        }
        for (int i=2;i<=Math.sqrt(num);i++) {
            if (num%i==0) {
                return false;
            }
        }
        return true;
    }

}

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    private static int max = 0;


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();

        ArrayList<Integer> oddList = new ArrayList<>();
        ArrayList<Integer> evenList = new ArrayList<>();


        for (int i = 0; i < n; i++) {
            int temp = scanner.nextInt();
            if (temp % 2 == 0) {
                evenList.add(temp);
            } else {
                oddList.add(temp);
            }
        }

        int[] odd = new int[oddList.size()];
        int[] even = new int[evenList.size()];

        for (int i = 0; i < oddList.size(); i++) {
            odd[i] = oddList.get(i);
        }

        for (int i = 0; i < evenList.size(); i++) {
            even[i] = evenList.get(i);
        }


        dp(odd, even, 0);
        System.out.println(max);
    }


    public static boolean isPrime(int item) {
        for (int i = 2; i <= Math.sqrt(item); i++) {
            if (item % i == 0) {
                return false;
            }
        }
        return true;
    }


    public static void dp(int[] odd, int[] even, int counter) {

        for (int i = 0; i < odd.length ; i++) {

            if (odd[i] != 0) {
                int a = odd[i];
                odd[i] = 0;

                for (int j = 0; j < even.length; j++) {

                    if (even[j] != 0) {
                        int b = even[j];
                        even[j] = 0;
                        
                        if (isPrime(a + b)) {
                            dp(odd, even, counter + 1);
                        }

                        even[j] = b;
                    }
                }

                odd[i] = a;
            }

        }

        max = Math.max(max, counter);
    }

}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 获取输入的正整数个数
        int n = in.nextInt();
        // 定义一个集合，用于存放这n个正整数中奇数
        List<Integer> jishu = new ArrayList<>();
        // 定义一个集合，用于存放这n个正整数中的偶数
        List<Integer> oushu = new ArrayList<>();
        // 读取输入的正整数
        for (int i = 0; i < n; i++) {
            int m = in.nextInt();
            if (m % 2 == 0) {
                //偶数
                oushu.add(m);
            } else {
                // 奇数
                jishu.add(m);
            }
        }
        // 查找素数伴侣，返回查找到的最大对数
        int max = findResult(jishu, oushu);
        // 输出最大对数
        System.out.println(max);
    }
    /**
     * 查找n个正整数中存在素数伴侣的最大对数.
     */
    private static int findResult(List<Integer> jishu, List<Integer> oushu) {
        // 定义找到的最大对数
        int max = 0;
        // 定义一个数组，用于存放偶数的伴侣，这个数组里面存放的是奇数列表中的值，默认0填充
        int[] oushuSoul = new int[oushu.size()];
        // 对奇数进行遍历，判断该奇数能否找到偶数伴侣
        for (int i = 0; i < jishu.size(); i++) {
            // 定义一个数组，用于存放偶数列表中的偶数是否被该奇数配对过
            boolean[] isPair = new boolean[oushu.size()];
            // 如果奇数和偶数能够形成最优配对，则max加1
            if (isPairSuccess(jishu.get(i), oushu, oushuSoul, isPair)) {
                max++;
            }
        }
        return max;
    }
    /**
     * 判断奇数 jishu,是否能够在oushu列表中形成最优配对
     */
    private static boolean isPairSuccess(int jishu, List<Integer> oushu,
                                         int[] oushuSoul,
                                         boolean[] isPair) {
        // 将这个奇数依次与偶数进行配对，看是否存在最优配对
        for (int i = 0; i < oushu.size(); i++) {
            // 如果两则相加为素数，切该位置还没有配对过，则可组成素数伴侣，但最优素数伴侣得继续进行条件判断
            if (isPrimeNumber(jishu + oushu.get(i)) && isPair[i] == false) {
                // 将该偶数设置为已配对过
                isPair[i] = true;
                // 匈牙利算法，先到先得，能让就让;如果该位置的偶数还没有奇数伴侣，则形成最佳素数伴侣(先到先得);
                // 如果该位置偶数已经有了奇数伴侣，那么就看这个奇数是否还能找到其他的偶数伴侣，如果能找到，
                // 就将该位置偶数让出(能让就让)
                if (oushuSoul[i] == 0 ||
                        isPairSuccess(oushuSoul[i], oushu, oushuSoul, isPair)) {
                    // 将该位置偶数伴侣添加到数组进行配对成功
                    oushuSoul[i] = jishu;
                    // 找到最优的素数伴侣了
                    return true;
                }
            }
        }
        return false;
    }
    /**
     * 判断一个数是否为素数.
     * 质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数
     */
    private static boolean isPrimeNumber(int num) {
        for (int i = 2; i < num; i++) {
            // 在2-num之间，只要存在一个数，使得num能被这个数整除，则num为非素数
            if (num % i == 0 ) {
                return false;
            }
        }
        // 上面没有返回false,则表明不存在一个数，使得num能被这个数整除，则num为素数,则返回true
        return true;
    }
}

import java.util.*;

public class Main {
    private static int res;
    private static List<List<Integer>> nextv;
    private static boolean[] vis;
    private static int[] match;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = Integer.valueOf(in.nextLine());
            int[] nums = new int[n];
            for (int i = 0; i < n; i++) {
                nums[i] = in.nextInt();
            }
            res = 0;
            solve(nums);
            System.out.println(res);
        }
    }
    
    private static void solve(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return;
        }
        // 素数 = 奇数 + 偶数
        // 把奇数、偶数各分为一组;
        // 如果奇数和偶数能组成素数伴侣, 就连一条边
        List<Integer> odd = new ArrayList<>();
        List<Integer> even = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (nums[i] % 2 == 0) {
                even.add(i);
            } else {
                odd.add(i);
            }
        }
        if (odd.size() == 0 || even.size() == 0) {
            return;
        }
        // 建二分图
        nextv = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nextv.add(new ArrayList<>());
        }
        for (int i = 0; i < odd.size(); i++) {
            int from = odd.get(i);
            for (int j = 0; j < even.size(); j++) {
                int to = even.get(j);
                int x = nums[from] + nums[to];
                if (isPrime(x)) {
                    nextv.get(from).add(to);
                }
            }
        }
        // 二分图最大匹配的匈牙利算法
        vis = new boolean[n];
        match = new int[n];
        for (int i = 0; i < n; i++) {
            match[i] = -1;
        }
        for (int i = 0; i < n; i++) {
            // 重置
            resetVis();
            if (dfs(i)) {
                res++;
            }
        }
    }
    
    private static void resetVis() {
        for (int i = 0; i < vis.length; i++) {
            vis[i] = false;
        }
    }
    
    private static boolean dfs(int from) {
        List<Integer> nextList = nextv.get(from);
        for (int i = 0; i < nextList.size(); i++) {
            int next = nextList.get(i);
            if (!vis[next]) {
                vis[next] = true;
                if (match[next] == -1) {
                    // 没有被匹配过
                    match[next] = from;
                    return true;
                } else {
                    // 被匹配过, 找增广路
                    boolean sgn = dfs(match[next]);
                    if (sgn) {
                        match[next] = from;
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
    private static boolean isPrime(int x) {
        if (x <= 1) {
            return false;
        }
        if (x == 2) {
            return true;
        }
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

/**
 * @author pengxin
 * @date 2022/4/1 15:59
 */
public class Main {

    /**
     * 4
     * 2 5 6 13
     *
     * 2 6
     * 5 13
     *
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {


        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ints = new int[n];
        for (int i = 0; i < n; i++) {
            ints[i] = sc.nextInt();
        }

        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (ints[i] % 2 == 1) {
                list1.add(ints[i]);
            } else {
                list2.add(ints[i]);
            }
        }

        // 匹配数
        int result = 0;

        // list1 匹配 list2的记录：key-list2的值，value-list1的值
        Map<Integer, Integer> matchMap = new HashMap<>(n);

        int size1 = list1.size();
        for (int i = 0; i < size1; i++) {

            // 每次list1来匹配，list2腾挪过程中，已经被匹配的list2的index集合，这个集合中的下标，在递归流程中需要跳过
            Set<Integer> usedIndexSet = new HashSet<>();

            if (match(list1.get(i), list2, matchMap, usedIndexSet)) {
                result++;
            }
        }
        System.out.println(result);
    }

    private static boolean match(int int1, List<Integer> list2, Map<Integer, Integer> matchMap, Set<Integer> usedIndexSet) {

        int size2 = list2.size();
        for (int j = 0; j < size2; j++) {

            // 已经被匹配的list2的index集合，不需要再匹配
            if (usedIndexSet.contains(j)) {
                continue;
            }

            Integer int2 = list2.get(j);

            if (isMatch(int1 + int2)) {

                usedIndexSet.add(j);

                if (matchMap.get(int2) == null || match(matchMap.get(int2), list2, matchMap, usedIndexSet)) {
                    matchMap.put(int2, int1);
                    return true;
                }
            }
        }

        return false;

    }

    private static boolean isMatch(int x) {
        int sqrt = (int) Math.sqrt(x);
        for (int i = 2; i <= sqrt; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

import java.util.*;
import java.io.*;

/**
 * 二分图,匈牙利算法
 */
public class Main{
    //参数中的偶数列表,作为全局变量便于传参
    private static ArrayList<Integer> evens = new ArrayList<>();
    
    public static void main(String[] args) throws IOException{
        //1.获取并存储数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        br.readLine();
        String[] nums = br.readLine().split(" ");
        ArrayList<Integer> odds = new ArrayList<>();//奇数列表
        //只有奇数和偶数的和才能为素数(除了2,条件已排除),正好适用二分图
        for(String a : nums){
            if(Integer.parseInt(a) % 2 == 0){//偶数
                evens.add(Integer.parseInt(a));
            }else{
                odds.add(Integer.parseInt(a));//奇数
            }
        }
        br.close();
        //2.数据准备
        //2.1定义一个偶数的伴侣数组,索引和偶数队列一一对应,值为伴侣的值,值为0表示没有伴侣
        int[] evenWife = new int[evens.size()];
        //2.2定义一个boolean数组,索引和偶数队列一一对应,记录一次奇数循环中已经匹配上的偶数
        boolean[] oddMatch;
        int count = 0;//统计伴侣对数
        
        //3.处理数据,为每一个奇数匹配伴侣
        for(int i=0; i<odds.size(); i++){//奇数循环,查找伴侣
            //每个奇数重置一遍,该数组作用避免死循环
            oddMatch = new boolean[evens.size()];
            //寻求最大路径,匈牙利算法
            if(find(odds.get(i), evenWife, oddMatch)){
                count++;
            }
        }
        System.out.println(count);
        
    }
    /*
     * 判断奇数x能否找到伴侣
     */
    private static boolean find(int x, int[] evenWife, boolean[] oddMatch){
        for(int i=0; i<evens.size(); i++){
            if(!oddMatch[i] && isPrime(evens.get(i) + x)){
                oddMatch[i] = true;//true表示该偶数i已被当前循环匹配为伴侣//防止闭环竞争
                /*
                 * 奇数x获得伴侣的两种情况:
                 * 1.偶数i没有伴侣==0,那就是我的了
                 * 2.偶数i有伴侣,但是i的伴侣(奇数)可以找到新的伴侣,那就把偶数i让出来(找不到就不让)
                 */
                if(evenWife[i] == 0 || find(evenWife[i], evenWife, oddMatch)){
                    evenWife[i] = x;//给偶数i添上伴侣
                    return true;
                }
            }
        }
        return false;
    }
     /*
     * 判断奇数x是否为素数
     */
    private static boolean isPrime(int x){
        for(int i=3; i<=Math.sqrt(x); i++){
            if(x%i == 0){
                return false;
            }
        }
        return true;
    }
    
    
}