论坛 › 难题征解 › 素数的偶数表示法

tprime 发表于 2008-6-30 10:19:39

素数的偶数表示法

:lol
对于任意大于6的偶数N, 存在两素数P1, P2使得 N = P1+P2.(有限范围内验证德巴赫猜想)
设D(N)为N分解为的素数和表示法总数
对于给定的N(N > 6 && N < 10^14), 求D(N)值
例如 6 = 3+3, 8 = 3 +5
D(6) = D(8) = 1
D(100000042)=218628,
D(100000044)=471539,
D(100000046)=223006,
//我的程序快调通了 D(10^9)需要500ms

无心人 发表于 2008-6-30 10:28:33

这东西有点水了

不如算N>10^16的吧

呵呵

mathe 发表于 2008-6-30 10:29:43

$10^16$那就很难了，复杂度应该是大于求指定范围内素数数目的

tprime 发表于 2008-6-30 10:38:25

回复 3# mathe 的帖子

算10^16 预计需要几个月, 采用经典分段筛法比较慢
有一些优化措施可以做.基于模30030, 510510等筛法
会比较快

mathe 发表于 2008-6-30 10:44:36

我觉得这个应该同求孪生素数的代码很类似。代码再怎么变，也脱离不了筛法

gxqcn 发表于 2008-6-30 10:45:10

我好像在哪儿看到：素数是用来乘的，不是用来加的！

所以哥德巴赫猜想才这么难解决。

tprime 发表于 2008-6-30 11:01:54

回复 5# mathe 的帖子

和孪生素数的代码几乎没有区别, 不过要比孪生素数稍微快一倍(N = 6k + 2, 4)
算孪生素数PI2(10^15)在我的机器上需要300小时

无心人 发表于 2008-6-30 11:36:04

使用双向筛
计算D(10^16)
则保守估计一个小时能筛1000亿素数
则需要100000小时时间

无心人 发表于 2008-6-30 11:36:54

应该能筛到20000亿/小时

tprime 发表于 2008-6-30 11:40:25

实际测试我的K生素数筛法
PI2(10^16) = 10304195697298 需要3000h
PI4(10^16) =25379433651需要340h
PI6(10^16) = 83217782 需要55h(结果有待验证)
至于计算PI6(10^17)目前需要800h

查看完整版本: 素数的偶数表示法