将任何数字表示为四个素数的总和

Question

我提出一个问题,将任何数字表示为四个素数的总和.

条件:

• 不允许使用任何类型的数据库.
• 最长执行时间:3秒
• 数字只有100,000
• 如果无法进行拆分,则返回-1

我做了什么 :

1. 使用Eratosthenes的筛子,我计算了所有素数,直到指定的数字.

2. 查找了一个名为Goldbach猜想的概念,它将偶数表示为两个素数的总和.

但是,我被困在那之外.任何人都可以帮我解决一下你可能采取的方法吗？

Eratosthenes的筛子花了两秒钟来计算高达100,000的素数.

Answer 1

随着时间的推移你仍然可以.由于Goldbach猜想,每个偶数大于或等于8可以表示为2,2和另外两个素数的总和.每个大于或等于9的奇数可以表示为2,3和另外两个素数的总和.找出素数并不需要太长时间.

编辑:实际上,你可以显着加快这个速度:对于任何偶数N,找到N-7小于或等于的最大素数并选择该素数和3,然后寻找另外两个素数以适合你的总和.对于任何奇数N,找到最大的素数大于或等于N-6并选择它和两个,然后再选择两个素数.