前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数组的最多素数个数

数组的最多素数个数

作者头像
benym
发布2022-07-14 16:50:18
3590
发布2022-07-14 16:50:18
举报
文章被收录于专栏:后端知识体系后端知识体系

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

第一行输入一个数字n

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

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

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

示例1:

代码语言:javascript
复制
3
5 3 7
6

# 解题思路

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

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

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

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

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

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

# Java代码1

代码语言:javascript
复制
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

代码语言:javascript
复制
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);
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-08-10,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • # 网易2021秋招-数组的最多素数个数
    • # 解题思路
      • # Java代码1
        • # Java代码2
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档