[出题]批处理验证哥得巴赫猜想

lxzzr

批处理验证哥得巴赫猜想

哥得巴赫猜想：任何一个大于6的偶数都是两个素数之和.

素数：就是在所有比1大的整数中,除了1和它本身以外,不再有别的因数.

偶数：自然数中，能被2整除的数是偶数，反之是奇数.


题：输入任何一个大于6的偶数，将其表示为两个素数之和.


注：DOS联盟论坛有相关的参考资料和贴子。

小罗

老师节日快乐,有个家伙老动我电脑,我怎么知道什么时间,有人在我不在时登陆过我电脑,即使是从锁定后登陆界面登陆的?

武庚

新手埋头学习中。

daohe

电脑太发达了。批处理太强悍了。牛人太多了。

opolokoi

虽然发现运算出现部分错误结果，但是还是很佩服各位老大这种高度。

gbw911

原帖由 lhjoanna 于 2009-4-24 22:24 发表
先构造素数表，感觉用批来构造素数表效率很低啊，哪位高手如果能用位来实现就好了。
我也来写一个，先构造素数表，效率问题，只构造了10000以内的。@echo off&setlocal enabledelayedexpansion
echo.&echo 正在构建 ...

输的结果有问题啊！把所有数之和等于所输入偶数的结果都输出了，修改一下更好

Batcher

999983应该怎样分解质因数？

mkl

18楼代码
请输入一个大于6的偶数：1000000
开始时间：22:04:42 结束时间：22:04:42
1000000=17+999983
复制代码

9楼代码
请输入一个整数(按i使用内置测试集，直接按回车退出): 999983
999983 是合数
复制代码

jackerloo2009

看来我还得好好学学数学哦。顶下各位版主了！真是不积小流，无以成江海啊！

beck1321

论坛逛得不多，但是每次来，都能看到各大高手的身手。。拜服

haolongo

支持版主一下，谢谢了。

batman

思路：利用牛顿迭代法快速求出数的平方根近似值，从而最大程度上减少循环次数，算法如下：
    首先我们设要求的这个数为a，它的平方根为x；然后我们一开始令x=a；然后我们进入一个
循环，不断的令x=(x+a/x)/2，就是令x等于 x和a/x的平均值，这样迭代了10次左右就可以得到a
的平方根x的近似值。
因此将本人12楼的代码再次提速如下：

@echo off&setlocal enabledelayedexpansion
rem write by batman on 2009-4-26 3:20 of bbs.bathome.net
set /p a=请输入一个大于6的偶数：
set "t=%time:~,-3%"
for /l %%a in (3,2,%a%) do (
    set /a b=a-%%a,n=0,c=a&call :lp %%a !b!
    if !n! equ 2 (
       echo 开始时间：%t% 结束时间：!time:~,-3!
       echo %a%=%%a+!b!&goto next
    )
)
:next
pause>nul&goto :eof 
:lp
for /l %%a in (1,1,10) do set /a c=(c+a/c)/2
for /l %%a in (3,2,%c%) do (
     if %%a neq %1 set /a d=%1%%%%a
     if !d! equ 0 goto :eof
)
set /a n+=1
if "%2" neq "" shift&goto lp
复制代码

[ 本帖最后由 batman 于 2009-4-26 03:29 编辑 ]

batman

回lhjoanna版主，可能是我的言语没有注意，还请兄弟原谅。但对于超大数来讲，要构建素数表，永远都会存在效率问题，这就
是我的本意。

lhjoanna

Re:batman
     呵，就此题来说，兄的代码确实能够比较高效的解决。我想如果能从这道题目挖掘出什么更深层的问题，那也就是素数的构建了。因为对素数的研究有许多的实际意义，比如数论、密码技术等。这也是一个公认的难题，如何在有限的空间进行更高效的求解素数。比如输出1-1亿内所有的素数，或者一个文件中包含成千上万个大数要判定是否为素数。为了把判定效率降低到线性水平，不可能对每一个数进行从头判断，构建素数表是必要的选择了。

inittab

原帖由 lhjoanna 于 2009-4-25 12:59 发表
采用位运算构造素数表，具体思路：比如构造10000以内的素数表，就用10000/32个变量来表示这10000个数的状态，每一个数都有32位，用每一位表示一种状态，1表示是素数，0表示非素数，这样就可以省下32倍的空间。比如判 ...

太厉害了。对移位运算和逻辑运算还不太明白。先下来收藏