中国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>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 ]

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

不过我是从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
请楼主告知这段代码是什么意思.??????????