批处理求1000以内的所有素数
求1000以内的所有素数最好还要有解释的,新手啊... [code]@echo off
setlocal ENABLEDELAYEDEXPANSION
:a
set /a num+=1
if %num%==1 goto a
for %%a in (2 3) do if %num%==%%a echo %%a&goto a
if %num%==1000 pause>nul&exit
set /a num2=num-1
for /l %%b in (2 1 %num2%) do (
set /a tp=%num%%%%%b
if !tp!==0 set tp2=a
)
set tp2=&if "%tp2%"=="" echo %num%
goto a[/code] [code]@echo off&setlocal enabledelayedexpansion
for %%i in (0 2 4 5 6 8) do set "_%%i=a"
echo 1-1000內的素數如下:>素數.txt
for /l %%a in (1,1,1000) do (
set "str=%%i"
if not defined _!str:~-1! (
set /a a=%%a/2+1,num=0
call :lp %%a
)
)
start 素數.txt
goto :eof
:lp
for /l %%i in (1,1,%a%) do (
set /a b=%1/%%i*%%i
if !b! equ %1 set /a num+=1
if !num! equ 2 goto :eof
)
if %num% lss 2 echo %1 >>素數.txt[/code] 二樓的代碼效率是個問題,完全可以不要驗證一個數所有的約數,除本身外只要約數大於兩個就可以判斷出不是素數了。 楼上的都是低效率 不是完全模拟,经过了人工处理
测试代码:[code]@echo off
setlocal enabledelayedexpansion
for /l %%i in (3 2 1000) do (
set flag=0
for /l %%j in (3 2 37) do (
set /a var=%%i%%%%j
if !var! EQU 0 set /a flag+=1
)
if !flag! LEQ 1 echo %%i
)
pause>nul[/code] 稍微修整:[code]@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
)
pause>nul[/code] for /l %%i in (1 3 999) do echo %%i 大家能不能给点翻译啊? [quote]原帖由 [i]youxi01[/i] 于 2008-10-31 22:25 发表 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=14024&ptid=2372][img]http://www.bathome.net/images/common/back.gif[/img][/url]
稍微修整:@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 %% ... [/quote]
体现出兄扎实的数学功底,真是望尘莫及啊! 怎么youxi的是从67开始?
回复 11楼 的帖子
呵呵,那是因为批处理一屏显示不了那么多如果在运行初期你就按ctrl+c,或者echo到一个文本文件就可以看到全部了 [quote]原帖由 [i]youxi01[/i] 于 2008-11-1 16:56 发表 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=14092&ptid=2372][img]http://www.bathome.net/images/common/back.gif[/img][/url]
呵呵,那是因为批处理一屏显示不了那么多
如果在运行初期你就按ctrl+c,或者echo到一个文本文件就可以看到全部了 [/quote]
if not "%1"=="more" call "%~0"|more&exit [quote]原帖由 [i]youxi01[/i] 于 2008-11-1 16:56 发表 [url=http://www.bathome.net/redirect.php?goto=findpost&pid=14092&ptid=2372][img]http://www.bathome.net/images/common/back.gif[/img][/url]
呵呵,那是因为批处理一屏显示不了那么多
如果在运行初期你就按ctrl+c,或者echo到一个文本文件就可以看到全部了 [/quote]
原来如此
写个用文件的
[code]@echo offsetlocal 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 (set flag=) else (>>ss.txt echo %%i)
)
type ss.txt
pause
goto :eof[/code]
品评一下 7 楼代码
大优点:以下两句使得速度大提
@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也是素数
是不是有挖墙脚之嫌了,闪
回复 6楼 的帖子
末位是5的也是素数?youxi01的代码有问题。995都出来了。[[i] 本帖最后由 myzwd 于 2009-3-2 23:52 编辑 [/i]] 素数包括数字2,2是唯一的属于偶数的素数。
回复 3楼 的帖子
3楼代码,刚好漏掉素数 2我也来一个
[code]@echo offsetlocal enabledelayedexpansion
echo 1
echo 2
set/a num=2
for /l %%i in (3 2 1000) do (
call :test %%i
if !flag!==1 echo %%i&set/a num+=1
)
echo 1~1000内共有素数 %num% 个。
pause>nul &goto :eof
:test
set /a flag=1
set /a b=%1/2
set /a count=0
for /l %%a in (1 1 !b!) do (
set /a yushu=%1 %% %%a
if !yushu! equ 0 set /a count=!count!+1
if !count! gtr 1 (set /a flag=0 & goto :eof)
)[/code] [quote]原帖由 [i]wxcute[/i] 于 2008-11-3 10:48 发表 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=14285&ptid=2372][img]http://bbs.bathome.net/images/common/back.gif[/img][/url]
@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 ... [/quote]
冰疼的代码,比上楼我的代码效率高多了,对冰疼的代码进行修改,不再写入文件。[code]@echo off
setlocal enableDelayedExpansion
set str=2&set/a num=1
echo 2
for /l %%i in (3 2 1000) do (
for %%j in (!str!) do (
set/a mod=%%i%%%%j
if !mod! equ 0 set flag=1
)
if defined flag (set flag=) else (echo %%i&set str=!str! %%i&set/a num+=1)
)
echo 1000以内的素数共有 %num% 个。
pause>nul
goto :eof[/code]
[[i] 本帖最后由 sjzong 于 2009-5-8 14:57 编辑 [/i]] 增加了一个判断 提高效率[code]@echo off
setlocal enableDelayedExpansion
set/p x=请输入需求 多大数字内的质数
set str=2&set/a num=1
echo 2
for /l %%i in (3 2 !x!) do (
for %%j in (!str!) do (
set/a mod=%%i%%%%j
if !mod! equ 0 set flag=1
)
if defined flag (set flag=) else (
echo %%i
set/a n=%%i*%%i
set/a num+=1
if !n! lss !x! set str=!str! %%i
)
)
echo !x!以内的素数共有 %num% 个。
pause[/code]
[[i] 本帖最后由 skuny 于 2011-1-13 19:31 编辑 [/i]]
回复 22楼 的帖子
22楼改得真好,效率大大提高。俺也贴一个
[code]@echo offsetlocal EnableExtensions
setlocal EnableDelayedExpansion
REM 时间:20:36 2011-01-12
REM 功能:求1000以内的质数.效率一般。
set /a n=1
set /a m=1
set /a p%n%=2
echo 2
set "flag="
for /L %%a in (3,2,1000) do (
call :PRIME %%a !m! flag
if "!flag!"=="TRUE" (
echo %%a
set /a n+=1
set /a temp=%%a*%%a
if !temp! lss 1000 (
set /a m+=1
set p!m!=%%a
)
)
)
echo 1000以内共有%n%个质数
pause
goto :EOF
:PRIME
for /l %%a in (1,1,!m!) do (
set /a yu=%1%%!p%%a!
if "!yu!"=="0" (
set "%3=FALSE"
goto :EOF
)
)
set "%3=TRUE"[/code] [i=s] 本帖最后由 techon 于 2011-5-15 09:28 编辑 [/i]
[quote]
@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
)
[/quote]
算法到可以 就是判断有误
拿个典型的数字 如 699 讲究效率的话,应该用Sieve of Eratosthenes(埃拉托斯特尼筛法),但是代码比较长[code]
@ECHO OFF
SETLOCAL ENABLEDELAYEDEXPANSION
REM Author: Demon
REM Date: 2011/5/29
REM Website: http://demon.tw
REM Algorithm: Sieve of Eratosthenes
REM Reference: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
SET /A limit = 1000
SET /A prime = 2
CALL :Init
CALL :SievePrime
CALL :Display
PAUSE & GOTO :EOF
:Display
FOR /L %%i IN (2, 1, %limit%) DO (
SET t=!arr[%%i]!
IF !t! NEQ 0 ECHO !t!
)
GOTO :EOF
:Init
FOR /L %%i IN (1, 1, %limit%) DO SET arr[%%i]=%%i
GOTO :EOF
:SievePrime
SET /A pow = prime * prime
IF %pow% LSS %limit% (
SET /A n = prime * 2
FOR /L %%i IN (!n!, %prime%, %limit%) DO SET arr[%%i]=0
CALL :NextPrime
GOTO :SievePrime
)
GOTO :EOF
:NextPrime
SET /A prime += 1
FOR /L %%i IN (%prime%, 1, %limit%) DO (
IF !arr[%%i]! NEQ 0 SET /A prime = %%i & GOTO :EOF
)
GOTO :EOF
[/code] 发一个素数查找的
有一定缺陷,理论上数字可以是2^31以内,但只能到13000左右。
原因是set命令只能有8K字符长度,超过8K的话bat设置的set命令全部清除,也就造成后面代码出错。
这个效率应该可以![code]@echo off&setlocal ENABLEDELAYEDEXPANSION
if %1.==. (set i=100) else set /a i=%1||exit/b
set time_0=!time!
set "p=2 3 5 7 11 13 17 19"
for %%a in (!p!) do (if %%a gtr !i! (exit/b) else echo %%a)
set i_0=!i:~0,-1!
set "p=3 7 11 13 17 19"
for /l %%a in (2,1,!i_0!) do (
for %%b in (1 3 7 9) do (
set p_0=!p!
set /a x_%%b=0
for %%c in (!p_0!) do (
if !x_%%b! equ 0 (
set /a p_1=%%a%%b %% %%c
if !p_1! equ 0 set /a x_%%b=1,p_0=1
)
)
if %%a%%b gtr !i! (echo 开始时间:!time_0!&echo 结束时间:!time!&exit/b) else (
if !x_%%b! equ 0 set "p=!p! %%a%%b"&echo %%a%%b
)
)
)
exit/b
[/code] 费马小定理 概率算法,秒杀~ [b]回复 [url=http://bbs.bathome.net/redirect.php?goto=findpost&pid=14024&ptid=2372]7#[/url] [i]youxi01[/i] [/b]
2也是质数(素数)[color=Red](素数又称质数,一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数,也就是素数;否则称为合数。)[/color]前辈的算法真的厉害!
页:
[1]