欢迎光临
我们一直在努力

计算机牛牛现在有一个包含 n 个正整数的数组 a ,牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数,牛牛想知道拆后(也可以一个数都不拆)这个数组最多能有多少个素数。-笔试面试资料

本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

这是qklbishe.com第6052 篇笔试面试资料
提供答案分析,通过本文《牛牛现在有一个包含 n 个正整数的数组 a ,牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数,牛牛想知道拆后(也可以一个数都不拆)这个数组最多能有多少个素数。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
牛牛现在有一个包含 n 个正整数的数组 a ,牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数,牛牛想知道拆后(也可以一个数都不拆)这个数组最多能有多少个素数。

牛牛现在有一个包含 n 个正整数的数组 a ,牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数,牛牛想知道拆后(也可以一个数都不拆)这个数组最多能有多少个素数。-笔试面试资料 零葬
对于1,它本来就不是素数,最多能拆成0个素数的和;
对于2和3,最多能拆成1个素数的和;
4 = 2 + 2,最多能拆成2个素数的和;
5 = 2 + 3,最多能拆成2个素数的和;
6 = 2 + 2 + 2,最多能拆成3个素数的和;
7 = 2 + 2 + 3,最多能拆成3个素数的和;
8  = 2 + 2 + 2 + 2,最多能拆成4个素数的和;
……
由此易知,从4开始,所有的数都可以拆成若干2和3的和,并且可以通是否有3来控制奇偶性。num%2==0时,有多少个2就有多少个素数,此时(num+1)%2==1,从num的求和式中随便挑一个2替换成3就能够凑出num+1,求和式中素数的个数不变,num+2只是又拆出一个2重复这个过程,此时num+2的求和式中相比num+1和num,素数增加一个。综上,每个数num最多可以拆成(int)num/2个素数相加。
如此一来,我们就可以通过遍历数组得到答案:

n = int(input()) arr = list(map(int, input().split())) ans = 0 for num in arr:     # 数组中的元素是1,2,3的时候不能拆     if num in [2, 3]:         ans += 1     elif num == 1:         # 1不需要拆,它本来就不是素数         pass     else:         # 其他元素最多能拆出num//2个素数         ans += num // 2 print(ans)


2021-01-16 23:02:33 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

赞(0)
未经允许不得转载: 京大飞辅助网程序员面试-区块链javago面经 » 计算机牛牛现在有一个包含 n 个正整数的数组 a ,牛牛可以将其中的每个数 a[i] 都拆成若干个和为 a[i] 的正整数,牛牛想知道拆后(也可以一个数都不拆)这个数组最多能有多少个素数。-笔试面试资料

相关推荐

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址