求1到1000所有素数的和 - 中国DOS联盟论坛 - 中国DOS联盟之联合DOS论坛

其实不得不爱版主原来写过一个,改改就能用了.


@echo off&setlocal enabledelayedexpansion
set t1=%time% %=开始计时=%
set sum=17&set n=3&set n1=3&set n2=5&set n3=7
set/p a= 2 3 5 7 <nul
for /l %%a in (9 2 99) do (
set/a a=%%a%%3,b=%%a%%5,c=%%a%%7
if not !a!==0 if not !b!==0 if not !c!==0 set/p= %%a<nul&set/a sum+=%%a&set/a n+=1&&set n!n!=%%a)
for /l %%a in (101 2 9999) do (
for /l %%b in (1,1,%n%) do (
set/a a=%%a%%n%%b
if !a!==0 set b=1)
if not !b!==1 set/p= %%a<nul&set/a sum+=%%a
set b=0)
set t2=%time%%=计时结束=%
echo/
echo 开始时间:%t1%
echo 结束时间:%t2%
echo 10000以内的素数和为：%sum%
pause

VB,C和批处理的运算机制应该不太一样.所以比较大的运算肯定高级语言效率高.

楼上很不错的代码, 效率高, 规律找得好, 加分~~~

俺要COPY下来收藏慢慢看。

从头至尾看下来

除了15楼的筛选法有些与众不同外

其它代码的核心算法都是大同小异的试除法

只是在利用的语法特性和剪枝上有些变化

这导致算法效率很难有数量级的提升

所以，我们还是应该多在核心算法上多下功夫

我建议下一目标应该是：有效时间内完成单个任意32位整数是否素数的判定

--------------------------------------------------------------------------------------------

下面的代码仍是基于16楼代码的变化形式

本来不想发的，只是觉得仍然有些新东西


@echo off
setlocal enabledelayedexpansion
set t1=%time% %=开始计时=%
set /a s=17, n=3, n1=3, n2=5, n3=7
for /l %%a in (9,2,99) do (
    set/a p=%%a%%3 * %%a%%5 * %%a%%7
    if !p! neq 0 (
        set/a s+=%%a, n+=1
        set n!n!=%%a
    )
)
for /l %%a in (101,2,9999) do (
    set p=1
    for /l %%b in (1,1,%n%) do (
        if !p! neq 0 set/a "p=(%%a%%n%%b)*p/p"
    )
    if !p! neq 0 set/a s+=%%a
)
set t2=%time%%=计时结束=%
echo/
echo 开始时间:%t1%
echo 结束时间:%t2%
echo 10000以内的素数和为：%s%
pause

16楼的代码在找规律上花了不少心血, 是不得不爱版主写的, 欣赏~~~

暂时叫这种方法为"素数相除法"吧, 也不知道对不对.

找到的这个规律还是有局限性的, 而且当取素数的范围超过1-10000, 就会出错, 必须再用101-1000以内或其他高位更多的素数除以10000以后的各数才能保证取到的为素数, 显然这种处理方法就不适宜处理更大的数了. 但求1-10000以内的素数效率还是很高的.



素数相除法: 先用10以内的素数除以100以内有各数, 得到1-100的素数, 再用1-100内的素数除以101-10000以内的数, 得到1-10000以内的素数.


下面是两种算法对求1-11000以内素数和的结果, 素数相除法因为没有采用更高位的素数除10000以后的数, 把一些非素数也判断成了素数. 素数和也更大.

筛法: 1-11000范围内素数和为:的6848586
素数相除法: 1-11000范围内素数和为:6890606

平时我们常用的是筛法求素数(算法在15楼), 但看了namejm版主4楼给出的页面链接印度计算机专家给出的新的算法, 说在处理更大的数时要快很多.

可是网页中给出的算法好像是用伪代码写的, 怎么看也看不懂. 先存好, 再细细去想吧~~~


素数判定算法 

(当且仅当n为素数时，最终输出数才为素数)

(当且仅当n为素数时，最终输出数才为素数) 
Input: integer n&gt;1
1. if ( n is the form of a^b, b&gt;1) output Composite;
2. r = 2;
3. while (r)
4. if (gcd(n,r)1) output Composite;
5. if (r is the prime)
6. let q be the largest factor of r-1;
7. if (q&gt;= 4 * (r^(1/2)) * log(n)) and (n^((r-1)/q))) mod r 1)
8. break;
9. r:=r+1;
10. {
11. for a := 1 to 2*(r^(1/2))*log(n);
12.if ((x-a)^n mod n(x^n-a)) and ((x-a)^n mod (x^r -1)(x^n-a))output Composite;
13.output Prime;

[ Last edited by pengfei on 2007-1-25 at 10:53 AM ]

关于以素数相除的算法起源很早，现在已很难考证

不过我是从willsort的代码中获取的素数相除的思想的

不得不爱的代码
http://www.cn-dos.net/forum/viewthread.php?tid=24951&fpage=0&highlight=&page=6

willsort的代码
http://www.cn-dos.net/forum/viewthread.php?tid=14580

----------------------------------------------------------------------

至于namejm给出链接

似乎有C语言的实现

但是国内根本就找不到

Google到的国外网址地震原因无法访问

------------------------------------------------------------

不过从国内讨论的结果来看

实现起来将很复杂

而且这是个概率算法

即判定结果是非确定性的

同时它的性能与实现方式严格相关

所以我基本上已不再考虑此算法

按qzwqzw兄来说, 这种概率算法没有他们讲的那么容易实现.

给出的伪代码算法, 看起来也是一知半解, 有点头疼的感觉~~~

if !a! equ 0 (
set flag=aaaa
goto :eof
) else (
set flag=bbbb)
)
请问楼主这段代码是什吗意思?

::::::::::::::::::Sub Function::::::::::::::::::::
:sss
请楼主告知这段代码是什么意思.??????????

第16楼　tao0610	发表于 2007-01-25 04:48
高级用户　发帖 218　积分 579
其实不得不爱版主原来写过一个,改改就能用了. @echo off&setlocal enabledelayedexpansion set t1=%time% %=开始计时=% set sum=17&set n=3&set n1=3&set n2=5&set n3=7 set/p a= 2 3 5 7 <nul for /l %%a in (9 2 99) do ( set/a a=%%a%%3,b=%%a%%5,c=%%a%%7 if not !a!==0 if not !b!==0 if not !c!==0 set/p= %%a<nul&set/a sum+=%%a&set/a n+=1&&set n!n!=%%a) for /l %%a in (101 2 9999) do ( for /l %%b in (1,1,%n%) do ( set/a a=%%a%%n%%b if !a!==0 set b=1) if not !b!==1 set/p= %%a<nul&set/a sum+=%%a set b=0) set t2=%time%%=计时结束=% echo/ echo 开始时间:%t1% echo 结束时间:%t2% echo 10000以内的素数和为：%sum% pause VB,C和批处理的运算机制应该不太一样.所以比较大的运算肯定高级语言效率高.

第17楼　pengfei	发表于 2007-01-25 05:38
银牌会员　发帖 485　积分 1,218　来自湖南.娄底
楼上很不错的代码, 效率高, 规律找得好, 加分~~~

第18楼　lzmyst	发表于 2007-01-25 05:50
新手上路　发帖 10　积分 19
俺要COPY下来收藏慢慢看。

第19楼　qzwqzw	发表于 2007-01-25 09:47
银牌会员　发帖 636　积分 2,343
从头至尾看下来除了15楼的筛选法有些与众不同外其它代码的核心算法都是大同小异的试除法只是在利用的语法特性和剪枝上有些变化这导致算法效率很难有数量级的提升所以，我们还是应该多在核心算法上多下功夫我建议下一目标应该是：有效时间内完成单个任意32位整数是否素数的判定 -------------------------------------------------------------------------------------------- 下面的代码仍是基于16楼代码的变化形式本来不想发的，只是觉得仍然有些新东西 @echo off setlocal enabledelayedexpansion set t1=%time% %=开始计时=% set /a s=17, n=3, n1=3, n2=5, n3=7 for /l %%a in (9,2,99) do ( set/a p=%%a%%3 * %%a%%5 * %%a%%7 if !p! neq 0 ( set/a s+=%%a, n+=1 set n!n!=%%a ) ) for /l %%a in (101,2,9999) do ( set p=1 for /l %%b in (1,1,%n%) do ( if !p! neq 0 set/a "p=(%%a%%n%%b)*p/p" ) if !p! neq 0 set/a s+=%%a ) set t2=%time%%=计时结束=% echo/ echo 开始时间:%t1% echo 结束时间:%t2% echo 10000以内的素数和为：%s% pause

第20楼　pengfei	发表于 2007-01-25 10:03
银牌会员　发帖 485　积分 1,218　来自湖南.娄底
16楼的代码在找规律上花了不少心血, 是不得不爱版主写的, 欣赏~~~ 暂时叫这种方法为"素数相除法"吧, 也不知道对不对. 找到的这个规律还是有局限性的, 而且当取素数的范围超过1-10000, 就会出错, 必须再用101-1000以内或其他高位更多的素数除以10000以后的各数才能保证取到的为素数, 显然这种处理方法就不适宜处理更大的数了. 但求1-10000以内的素数效率还是很高的. 素数相除法: 先用10以内的素数除以100以内有各数, 得到1-100的素数, 再用1-100内的素数除以101-10000以内的数, 得到1-10000以内的素数. 下面是两种算法对求1-11000以内素数和的结果, 素数相除法因为没有采用更高位的素数除10000以后的数, 把一些非素数也判断成了素数. 素数和也更大. 筛法: 1-11000范围内素数和为:的6848586 素数相除法: 1-11000范围内素数和为:6890606 平时我们常用的是筛法求素数(算法在15楼), 但看了namejm版主4楼给出的页面链接印度计算机专家给出的新的算法, 说在处理更大的数时要快很多. 可是网页中给出的算法好像是用伪代码写的, 怎么看也看不懂. 先存好, 再细细去想吧~~~ 素数判定算法 (当且仅当n为素数时，最终输出数才为素数) (当且仅当n为素数时，最终输出数才为素数) Input: integer n>1 1. if ( n is the form of a^b, b>1) output Composite; 2. r = 2; 3. while (r) 4. if (gcd(n,r)1) output Composite; 5. if (r is the prime) 6. let q be the largest factor of r-1; 7. if (q>= 4 * (r^(1/2)) * log(n)) and (n^((r-1)/q))) mod r 1) 8. break; 9. r:=r+1; 10. { 11. for a := 1 to 2(r^(1/2))log(n); 12.if ((x-a)^n mod n(x^n-a)) and ((x-a)^n mod (x^r -1)(x^n-a))output Composite; 13.output Prime; [ Last edited by pengfei on 2007-1-25 at 10:53 AM ]

第21楼　qzwqzw	发表于 2007-01-25 10:31
银牌会员　发帖 636　积分 2,343
关于以素数相除的算法起源很早，现在已很难考证不过我是从willsort的代码中获取的素数相除的思想的不得不爱的代码 http://www.cn-dos.net/forum/viewthread.php?tid=24951&fpage=0&highlight=&page=6 willsort的代码 http://www.cn-dos.net/forum/viewthread.php?tid=14580 ---------------------------------------------------------------------- 至于namejm给出链接似乎有C语言的实现但是国内根本就找不到 Google到的国外网址地震原因无法访问 ------------------------------------------------------------ 不过从国内讨论的结果来看实现起来将很复杂而且这是个概率算法即判定结果是非确定性的同时它的性能与实现方式严格相关所以我基本上已不再考虑此算法

第22楼　pengfei	发表于 2007-01-25 10:48
银牌会员　发帖 485　积分 1,218　来自湖南.娄底
按qzwqzw兄来说, 这种概率算法没有他们讲的那么容易实现. 给出的伪代码算法, 看起来也是一知半解, 有点头疼的感觉~~~

第23楼　stornager	发表于 2007-04-02 04:38
中级用户　发帖 131　积分 328
if !a! equ 0 ( set flag=aaaa goto :eof ) else ( set flag=bbbb) ) 请问楼主这段代码是什吗意思?

第24楼　stornager	发表于 2007-04-02 04:46
中级用户　发帖 131　积分 328
::::::::::::::::::Sub Function:::::::::::::::::::: :sss 请楼主告知这段代码是什么意思.??????????