素数的偶数表示法

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

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

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

×

对于任意大于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

算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

和孪生素数的代码几乎没有区别, 不过要比孪生素数稍微快一倍(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

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

[讨论] 素数的偶数表示法

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

回复 3# mathe 的帖子

回复 5# mathe 的帖子