批处理求1000以内的所有素数

wxcute

大优点：
以下两句使得速度大提
@echo off 2>nul 3>nul
set /a 1/^(%%i%%%%j^)||

小缺点：
LEQ 1，应改成 LEQ 0 或 LSS 1 吧，呵呵
11 楼所提问题不是因为显示不下吧，XP CMD 默认缓冲 300 行，而千以内的素数有百来个完全可以显示得下

改后也还有问题
当 %%i 与 %%j 相同时会使 set /a 1/^(%%i%%%%j^) 除数为 0，得 flag=1
所以 3-37 中的素数全会被剔除，加个判断就好了 if %%j lss %%i 或 if %%j neq %%i

开头加个 echo 2 ，2也是素数
是不是有挖墙脚之嫌了，闪

myzwd

末位是5的也是素数？youxi01的代码有问题。995都出来了。

[ 本帖最后由 myzwd 于 2009-3-2 23:52 编辑 ]

keen

素数包括数字2，2是唯一的属于偶数的素数。

sjzong

3楼代码，刚好漏掉素数 2

sjzong

1. @echo off
   
2. setlocal enabledelayedexpansion
   
3. echo 1
   
4. echo 2
   
5. set/a num=2
   
6. for /l %%i in (3 2 1000) do (
   
7. call :test %%i
   
8. if !flag!==1 echo %%i&set/a num+=1
   
9. )
   
10. echo 1~1000内共有素数 %num% 个。
    
11. pause>nul &goto :eof
    
12. 
    
13. :test
    
14. set /a flag=1
    
15. set /a b=%1/2
    
16. set /a count=0
    
17. for /l %%a in (1 1 !b!) do (
    
18.   set /a yushu=%1 %% %%a
    
19.   if !yushu! equ 0 set /a count=!count!+1
    
20.   if !count! gtr 1 (set /a flag=0 & goto :eof)
    
21. )

复制代码

sjzong

原帖由 wxcute 于 2008-11-3 10:48 发表
@echo off
setlocal enableDelayedExpansion
>ss.txt echo 2
for /l %%i in (3 2 1000) do (
　for /f %%j in (ss.txt) do (
　　set/a mod=%%i%%%%j
　　if !mod! equ 0 set flag=1
　)
　if defined flag  ...

冰疼的代码，比上楼我的代码效率高多了，对冰疼的代码进行修改，不再写入文件。

1. @echo off
   
2. setlocal enableDelayedExpansion
   
3. set str=2&set/a num=1
   
4. echo 2
   
5. for /l %%i in (3 2 1000) do (
   
6. for %%j in (!str!) do (
   
7. 　set/a mod=%%i%%%%j
   
8. 　if !mod! equ 0 set flag=1
   
9. )
   
10. if defined flag (set flag=) else (echo %%i&set str=!str! %%i&set/a num+=1)
    
11. )
    
12. echo 1000以内的素数共有 %num% 个。
    
13. pause>nul
    
14. goto :eof

复制代码

[ 本帖最后由 sjzong 于 2009-5-8 14:57 编辑 ]

skuny

增加了一个判断 提高效率

1. @echo off
   
2. setlocal enableDelayedExpansion
   
3. set/p x=请输入需求 多大数字内的质数
   
4. set str=2&set/a num=1
   
5. echo 2
   
6. for /l %%i in (3 2 !x!) do (
   
7.         for %%j in (!str!) do (
   
8.             set/a mod=%%i%%%%j
   
9.          　if !mod! equ 0 set flag=1
   
10.         )
    
11.        if defined flag (set flag=) else (
    
12.                                     echo %%i
    
13.                                     set/a n=%%i*%%i
    
14.                                     set/a num+=1
    
15.                                     if !n! lss !x! set str=!str! %%i
    
16.                                     )
    
17. )
    
18. echo !x!以内的素数共有 %num% 个。
    
19. pause

复制代码

[ 本帖最后由 skuny 于 2011-1-13 19:31 编辑 ]

mac007cn

22楼改得真好，效率大大提高。

mac007cn

1. @echo off
   
2. setlocal EnableExtensions
   
3. setlocal EnableDelayedExpansion
   
4. 
   
5. REM 时间：20:36 2011-01-12
   
6. REM 功能：求1000以内的质数.效率一般。
   
7. 
   
8. set /a n=1
   
9. set /a m=1
   
10. set /a p%n%=2
    
11. echo 2
    
12. set "flag="
    
13. for /L %%a in (3,2,1000) do (
    
14.         call :PRIME %%a !m! flag
    
15.         if "!flag!"=="TRUE" (
    
16.                 echo %%a
    
17.                 set /a n+=1
    
18.                 set /a temp=%%a*%%a
    
19.                 if !temp! lss 1000 (
    
20.                         set /a m+=1
    
21.                         set p!m!=%%a
    
22.                 )
    
23.         )
    
24. )
    
25. echo 1000以内共有%n%个质数
    
26. pause
    
27. goto :EOF       
    
28.        
    
29. :PRIME
    
30. for /l %%a in (1,1,!m!) do (
    
31.         set /a yu=%1%%!p%%a!
    
32.         if "!yu!"=="0" (
    
33.                 set "%3=FALSE"
    
34.                 goto :EOF
    
35.         )
    
36. )
    
37. set "%3=TRUE"

复制代码

techon

@echo off 2>nul 3>nul
setlocal enabledelayedexpansion
for /l %%i in (3 2 1000) do (
        set flag=0
        for /l %%j in (3 2 37) do set /a 1/^(%%i%%%%j^) ||set/a flag+=1
        if !flag! LEQ 1 echo %%i
)

算法到可以 就是判断有误

拿个典型的数字 如 699

Demon

讲究效率的话，应该用Sieve of Eratosthenes（埃拉托斯特尼筛法），但是代码比较长

1. 
   
2. @ECHO OFF
   
3. SETLOCAL ENABLEDELAYEDEXPANSION
   
4. 
   
5. REM Author: Demon
   
6. REM Date: 2011/5/29
   
7. REM Website: http://demon.tw
   
8. REM Algorithm: Sieve of Eratosthenes
   
9. REM Reference: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
   
10. 
    
11. SET /A limit = 1000
    
12. SET /A prime = 2
    
13. 
    
14. CALL :Init
    
15. CALL :SievePrime
    
16. CALL :Display
    
17. PAUSE & GOTO :EOF
    
18. 
    
19. :Display
    
20.     FOR /L %%i IN (2, 1, %limit%) DO (
    
21.         SET t=!arr[%%i]!
    
22.         IF !t! NEQ 0 ECHO !t!
    
23.     )
    
24. GOTO :EOF
    
25. 
    
26. :Init
    
27.     FOR /L %%i IN (1, 1, %limit%) DO SET arr[%%i]=%%i
    
28. GOTO :EOF
    
29. 
    
30. :SievePrime
    
31.     SET /A pow = prime * prime
    
32.     IF %pow% LSS %limit% (
    
33.         SET /A n = prime * 2
    
34.         FOR /L %%i IN (!n!, %prime%, %limit%) DO SET arr[%%i]=0
    
35.         CALL :NextPrime
    
36.         GOTO :SievePrime
    
37.     )
    
38. GOTO :EOF
    
39. 
    
40. :NextPrime
    
41.     SET /A prime += 1
    
42.     FOR /L %%i IN (%prime%, 1, %limit%) DO (
    
43.         IF !arr[%%i]! NEQ 0 SET /A prime = %%i & GOTO :EOF
    
44.     )
    
45. GOTO :EOF
    

复制代码

lincc0519

发一个素数查找的
有一定缺陷，理论上数字可以是2^31以内，但只能到13000左右。
原因是set命令只能有8K字符长度，超过8K的话bat设置的set命令全部清除，也就造成后面代码出错。
这个效率应该可以！

1. @echo off&setlocal ENABLEDELAYEDEXPANSION
   
2. if %1.==. (set i=100) else set /a i=%1||exit/b
   
3. set time_0=!time!
   
4. set "p=2 3 5 7 11 13 17 19"
   
5. for %%a in (!p!) do (if %%a gtr !i! (exit/b) else echo %%a)
   
6. set i_0=!i:~0,-1!
   
7. set "p=3 7 11 13 17 19"
   
8. for /l %%a in (2,1,!i_0!) do (
   
9.     for %%b in (1 3 7 9) do (
   
10.         set p_0=!p!
    
11.         set /a x_%%b=0
    
12.         for %%c in (!p_0!) do (
    
13.             if !x_%%b! equ 0 (
    
14.                set /a p_1=%%a%%b %% %%c
    
15.                if !p_1! equ 0 set /a x_%%b=1,p_0=1
    
16.             )
    
17.         )
    
18.         if %%a%%b gtr !i! (echo 开始时间:!time_0!&echo 结束时间:!time!&exit/b) else (
    
19.            if !x_%%b! equ 0 set "p=!p! %%a%%b"&echo %%a%%b
    
20.         )
    
21.     )
    
22. )
    
23. exit/b
    

复制代码

lllsoslll

费马小定理 概率算法，秒杀~

Gin_Q

回复 7# youxi01


    2也是质数（素数）（素数又称质数，一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数，也就是素数；否则称为合数。）前辈的算法真的厉害！