哥德巴赫奇数猜想计算

tprime · 发表于 2009-2-2 09:55:57

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

奇数猜想介绍
http://baike.baidu.com/view/1808.htm

现在的问题：对于给定的奇数N(N >= 9, N < 10^9)
求出三元数(P1,P2,P3)的数目T(N), 满足 P1 + P2 + P3 = N
且P1 <= P2 <= P3.

程序刚完成，性能不满意，计算范围也太小。

无心人 · 发表于 2009-2-2 14:04:25

筛法？

tprime · 发表于 2009-2-2 15:27:20

计算规模较小筛法都不用了
主要还是算法和代码优化吧

无心人 · 发表于 2009-2-2 15:49:53

10^9大小的素数用一个字节保存30k + 1..29内的素数
大概需要33333333字节保存
即32M的信息
而预先生成这个文件
不会超过30秒
甚至如果利用这个论坛的高效程序
10秒也可以

然后每次计算可以把这个文件读入内存

无心人 · 发表于 2009-2-2 15:54:55

至于具体的搜索某个奇数N的信息
假设固定首项素数是P
则问题转化成N - P
的哥德巴赫猜想的解数
仅是一个(N - P) / 60 个字节的线性搜索过程

如果有快速的位移动算法
则有很精妙的一个解法！！！！

如果采取预先计算的方法
更有一个特别快的算法
不过，需要占很大的内存
有4G内存可以考虑

tprime · 发表于 2009-2-2 15:56:37

你这个算法性能不会太好，试试计算10^7+1就知道了

无心人 · 发表于 2009-2-2 16:02:03

假设抛弃整体计算

对某个偶数N计算哥德巴赫解数量
先获得小于等于N的素数的位数组
其长度是N, 起始数字是0
0表示非，1表示是
则假设正序排列的数组是A1
对A1倒序，得到A2
求A = A1 and A2 逐位与
则，A数组的1的数量即为解的数量

tprime · 发表于 2009-2-2 17:03:36

我的程序就是你基于你上面算法的
实现, 性能依旧不满意, 不知是否有更好
的办法

无心人 · 发表于 2009-2-2 17:48:16

你让别人花金币买你的代码给你修改
呵呵

无心人 · 发表于 2009-2-2 17:50:25

不是代码？
给出代码来

账号		自动登录	找回密码
密码			欢迎注册

[原创] 哥德巴赫奇数猜想计算

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。