首页 > 试题广场 >

最少素数拆分

[编程题]最少素数拆分
  • 热度指数：4092 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。
素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

提示
哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。

示例1

输入

3

输出

1

说明

3本身就是1个素数
示例2

输入

6

输出

2

说明

6可以表示为3 + 3，注意同样的素数可以使用多次

备注:
算法知识视频讲解
开通博客
头像 _黄歪歪_B站录播
发表于 2020-02-11 15:31:40
暴力解法：最暴力的做法是DFS枚举素数累加，但复杂度太大根据哥德巴赫猜想，我们知道答案最大为3，因此可以先判断N本身是不是素数，然后暴力判断是否可以分解成两个素数的和，如果不行的话答案就是3。 bool IsPrime(int N) { if (N < 2) { ret 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 不会做题的小菜鸡
发表于 2021-08-21 12:38:31
思路 题目分析 题目要求我们在给定正整数N的情况下，求出用素数相加得到N，所需要的最少的素数个数 根据哥德巴赫猜想，大于2的偶数都可以拆分成两个素数之和（暂时未找到反例），所以我们可以直接用这个猜想。 本题的关键在于，对于一个数字N，看似要找的素数的个数可以有很多个，但是经过数学推理，其实这个最 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ZiRuio
发表于 2021-10-10 17:31:57
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 判断给定的正整数最少能表示成多少个素数的和 * @param N int整型 给定的正整数 * @return int整型 */ int isPrime(int N){ if(N< 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 小洋芋热爱NLP
发表于 2021-09-09 21:49:59
- 题目描述：- 题目链接： https://www.nowcoder.com/practice/07d6df2014184decb329de777ba7ff51?tpId=196&&tqId=37215&rp=1&ru=/ta/job-code-total& 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-03 14:59:22
题目描述现在给定一个正整数N，牛牛希望知道N最少表示成多少个素数的和。素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 提示哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。 方法一：暴力解法 求解思路对于本题求解N最少能表示成多少 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-04 17:30:30
思路： 题目的主要信息： 求一个整数N最少能够被拆分为多少个素数相加 哥德巴赫猜想：任意大于2的偶数都可以拆分成两个质数之和 根据哥德巴赫猜想，我们的结果res只会有三种情况： res=1res = 1res=1，N本身就是素数 res=2res = 2res=2，N是一个大于2的偶数，或者N 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-09-03 20:10:40
思路： 题目的主要信息：题目比较简短，需要注意的是哥德巴赫猜想，任意大于2的偶数都可以拆分成两个质数之和。该猜想尚未严格证明，但暂时没有找到反例。 已知的信息有一个整数N，需要计算N能表示为多少个素数的和，并返回个数 需要注意的是2是唯一的偶质数 方法一：数学方法 首先判断N是否为素数，分为两种 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

基础数学 递归
难度：
8条回答 7570浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最少素数拆分

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号