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

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

第一行输入一个数字n

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

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

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

示例1:

1
2
3
3
5 3 7
6

解题思路

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

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

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

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

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

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

Java代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}
}
打赏了解一下?
0%