首页 文章

找到与给定值相加的最小素数

提问于
浏览
2

我想找到总和给定值的最小素数集,例如9 = 7 2(不是3 3 3) .

我已经使用sieve of eratosthens生成了一个素数数组

我按降序遍历数组,以获得小于或等于给定数字的数组最大素数 . 如果数字是奇数,这很好用 . 但是对于偶数而言则失败,例如122 = 113 7 2但122 = 109 13 .

Golbach's Conjecture我们知道任何偶数都可以表示为两个素数的两个和 . 因此,如果数字是偶数,我们可以直接返回2作为输出 .

但我试图找出除蛮力以外的方法来找到最小素数 .

1 回答

  • 7

    虽然你的问题没有这么说,但我认为你正在寻找具有最小基数的素数集 .

    如果n是偶数,则按顺序考虑素数p,2,3,5,......;最终n - p将是素数,因此n是两个素数的总和 . 这个过程通常收敛得非常快,两个素数中较小的一个很少大于1000(通常比那个小得多) .

    如果n是奇数,并且n - 2是素数,则n是素数2和n - 2的总和 .

    如果n是奇数,并且n-2不是素数,则n-3是偶数,并且可以写为两个素数之和,如上所述 .

    因此,您总能找到两个或三个素数,它们总和到任何大于3的目标n .

相关问题