Edu 12 --- Simple Subset -- 题解 （一个比较巧妙的思维算法题）

Simple Subset：

题解： 

思路解析：

        题目要求任意两个数的和为质数，那我们最坏情况就是任意选择一个数，此时子集为最大。

        如果子集中有两个奇数或者偶数，他们两个之和一定会被2整除，那么我们只能选择一奇一偶。

        如果多个奇数都为1的话，他们两两之和刚好为奇数，就是全部选择1也可以作为一种答案。

        那么我们全部选择1的话，我们还可以选择一个数恰好加上1就变为质数。

        这样就分析出了这道题的四种情况，处理质数时，可以预先通过欧拉筛处理。

代码实现：

import java.io.*;
import java.math.BigInteger;
import java.util.*;


public class Main {
    public static void main(String[] args) throws IOException {
        boolean[] isprime = new boolean[2000005];
        int[] prime = new int[150000];
        int tot = 0;
        for (int i = 2; i <= 2000000; i++) {
            if (!isprime[i]) prime[++tot] = i;
            for (int j = 1; j <= tot && prime[j] * i <= 2000000; j++) {
                isprime[prime[j] * i] = true;
                if (i % prime[j] == 0) break;
            }
        }
        int cnt = 0;
        int n = f.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = f.nextInt();
            if (a[i] == 1) cnt++;
        }
        int loop = 0;
        int ans = 1;
        if (cnt > 0) {loop = 2; ans = cnt;}
        int l = 0;
        int r = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (!isprime[a[i] + a[j]] && 2 > ans) {ans = 2;loop = 1; l = i; r = j; break;}
            }
            if (r != 0) break;
        }

        int id = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) continue;
            boolean st = isprime[a[i] + 1];
            if (!st){
                if (cnt + 1 > ans){
                    loop = 3;
                    ans = cnt + 1;
                    id = i;
                }
                break;
            }
        }
        w.println(ans);
        if (loop == 0){
            w.println(a[0]);
        } else if (loop == 1) {
           w.println(a[l] + " " + a[r]);

        } else if (loop == 2) {
            for (int i = 0; i < cnt; i++) {
                w.print(1 + " ");
            }
        } else {
            for (int i = 0; i < cnt; i++) {
                w.print(1 + " ");
            }
            w.print(a[id]);
        }
        w.flush();
        w.close();

    }


    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}