网易2021秋招-数组的最多素数个数

题目

第一行输入一个数字n

第二行输入n个数字，求这n个数字最多能够拆解为多少个素数，且数字拆解之后素数之后等于数字本身。如5可以拆解为2，3；3本身为素数；7可以拆解为2，2，3

第三行输出数组最多能够拆解成的素数个数

最多1e6个数，每个数字最大为1e9，1不是素数

示例1：

3
5 3 7
6

解题思路

观察题目可知，当2的数量最多的时候，数组就拥有最多的素数个数。

考虑数字范围，需要通过long存储结果，因为累加肯定是超过了int范围

可以通过判断数字的奇数和偶数来分别进行计算：

偶数情况直接除以2，奇数情况减去3再除以2，再+1个即可

观察可知，上面的奇数情况可以直接合并为数字除以2即可，因为减去3也是减去的一个数，这个数最后还是要加回来的。

所以对每个数字除以2累加即可得到答案。

Java代码1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long sum = 0;
        int n = Integer.parseInt(sc.nextLine().trim());
        Main main = new Main();
        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            sum += main.countSu(num);
        }
        System.out.println(sum);
    }

    public long countSu(int num) {
        long sum = 0;
        if (num % 2 == 0) {
            sum += num / 2;
        } else {
            sum += ((num - 3) / 2) + 1;
        }
        return sum;
    }
}

Java代码2

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long res = 0;
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            res += sc.nextInt() >> 1;
        }
        System.out.println(res);
    }
}