我想找到总和给定值的最小素数集合,例如9 = 7 + 2(不是3 + 3 + 3).
我已经使用eratosthens筛子生成了一系列素数
我按降序遍历数组,以获得小于或等于给定数字的数组最大素数.如果数字是奇数,这很好用.但是偶数失败,例如122 = 113 + 7 + 2但122 = 109 +13.
从Golbach's猜想我们知道任何偶数都可以表示为两个素数的两个和.因此,如果数字是偶数,我们可以直接返回2作为输出.
但我试图找出除蛮力以外的方法来找到最小素数.
虽然你的问题没有这么说,但我认为你正在寻找具有最小基数的素数集.
如果n是偶数,则按顺序考虑素数p,2,3,5 ,......; 最终n - p将是素数,因此n是两个素数的总和.这个过程通常收敛得非常快,两个素数中较小的一个很少大于1000(通常比那个小得多).
如果n是奇数,并且n - 2是素数,则n是素数2和n - 2 的总和.
如果n是奇数,并且n -2不是素数,则n -3是偶数,并且可以写为两个素数之和,如上所述.
因此,您总能找到两个或三个素数,它们总和到任何大于3的目标n.