[百度][6,N]之内的所有素数中,两两之和为偶数的那些偶数


RT
其中N是个自然数,请给出算法描述,代码与时间复杂度分析。
已邀请:

SuiterChik - 烫烫烫烫烫烫烫烫烫烫烫烫烫

赞同来自: 邹博 LostOsiris 小楼昨夜听春雨 paladintyrion


==========================

声明:以下是我不负责任的瞎扯

首先要知道一个东西:
要判断一个数字是否为素数所要花费的时间是O(1)
如果你不知道这个,那么随便拿一本厚一点的算法书(注意,不是数据结构书),一般会在“随机算法”章节

==========================================
解法一(从素数角度出发):
首先,任何一个大于6的素数都可以写成6n±1的形式,为什么呢?因为任何一个数都可以写成6n, 6n+1,6n+2, 6n+3, 6n+4, 6n+5这几个形式,而其中6n, 6n+2, 6n+3, 6n+4这几个形式的数都不可能是素数,因为都能被2或3整除。而6n+5实际上也可以看做是6n-1,证明完毕。
但是这是一个必要不充分条件,也就是

一个数是素数,则一定可以写成6n±1中的一个形式
但是一个数可以写成6n±1形式,但他不一定是素数

所以我们要加入素性判断

然后你就在[6, N]这个区间中寻找满足6n±1形式的数,然后对这些数进行素性判断,最后就得到[6, N]区间的所有素数的
得到所有素素,只需要对他们两两求和就行啦。

复杂度分析比较麻烦,涉及到[6, N]中有多少个素数,我不会
但是其复杂度会在O(N)到O(N^2)以内

============================================
解法二(从和角度出发):
你听说过哥德巴赫猜想吗?

哥德巴赫猜想:任一大于2的整数都可写成两个质数之和。
欧拉对这个猜想等价出了另外一个版本:即任一大于2的偶数都可写成两个素数之和

所以,你只需要找到[6, N]区间内最大的两个素数,我假设为p和q,那么满足题目所求的数就在[18, p+q]区间内的所有偶数
注:18=7+11,此外这里有bug的,留后面说

现在的问题是,找到最大的那两个素数需要的时间是多久?
这涉及到一个问题:
两个相邻的素数间隔是多大?
这个问题似乎现在也没有解决,不过你可以从N往下一个一个按照6n±1地形式进行素性测试找出最大那两个的嘛(好丢脸的想法,逃)

好了,找到区间的上界了(也就是p+q),那么剩下一个BUG:题目说“两两之和”,所以这些偶数就不能是同一个素数相加啦,那你对这些偶数除2,然后素性判断就行啦(好丢脸,应该有更好的办法)

其实这里面最致命的BUG是:
我们使用了一个未被证明的猜想

但是你要这么想,我的算法是基于这个猜想了,要是出了问题能说明这个猜想不成立,那么...........................

你还去百度干什么

===================================

再次声明:
以上是我瞎扯的,别轻信=。=

要回复问题请先登录注册