バッチファイルでProject Euler（33）

Problem 12

エラトステネスのふるいのように約数の個数を求めるとさらに速くなります。ここの下のほうで説明した方法とだいたい同じです。ただし、下の段には素因数分解を記憶しておくのではなく、約数の個数を記憶しておきます。具体的には、まず1を代入しておき、pで割り切れることが分かったら、何乗で割り尽くせるか調べて、e乗ならe + 1を掛けます。
これで13分。

@echo off

setlocal
call :get_time
set /a t0 = %ERRORLEVEL%
set /a N = 500
set /a L = 500
set /a M = %L% * 2 + 1
call :make_primes ps %M%
call :solve
echo %ERRORLEVEL%
call :get_time
set /a t = %ERRORLEVEL% - %t0%
echo %t:~0,-2%.%t:~-2%s
exit /b 0

:solve
    setlocal
    set /a begin = 2
    set /a max_index = %ps.size%
    set /a max_prime = "ps_%max_index%"
    :loop_solve
        echo %begin% %time%
        set /a end = %begin% + %L%
        call :sieve %begin% %end%
        if %ERRORLEVEL% == 0 set /a begin += %L% - 1 & goto :loop_solve
    
    set /a n = %begin% + %ERRORLEVEL% - 1
    set /a m = %n% * (%n% + 1) / 2
    exit /b %m%

:sieve
    set /a begin = %1
    set /a end = %2
    set /a end_1 = %2 - 1
    call :range a %begin% %end%
    set /a i0 = %begin% %% 2
    for /L %%i in (%i0%, 2, %L%) do set /a a_%%i /= 2
    set /a b.size = %L%
    call :fill_vector b 1
    set /a k = 0
    set /a p = 2
    :loop_sieve
        set /a q0 = (%begin% + %p% - 1) / %p% * %p%
        for /L %%q in (%q0%, %p%, %end_1%) do call :div_pow %%q %p%
        set /a k += 1
        set /a p = "ps_%k%"
        set /a p_sq = %p% * %p%
        if %p_sq% LSS %end% goto :loop_sieve
    
    set /a k = 0
    set /a max_index = %ps.size%
    set /a p_max = "ps_%max_index%"
    :loop_sieve2
        set /a ak = "a_%k%"
        set /a bk = "b_%k%"
        if %ak% GTR 1 set /a b_%k% *= 2
        if %ak% GTR %p_max% call :push_vector ps %bk%
        set /a k += 1
        if %k% LSS %L% goto :loop_sieve2
    
    set /a k = 0
    :loop_sieve3
        set /a bk_prev = "b_%k%"
        set /a k += 1
        set /a bk = "b_%k%"
        set /a ndiv = %bk_prev% * %bk%
        if %ndiv% GTR %N% exit /b %k%
        if %k% LSS %L% goto :loop_sieve3
    exit /b 0

:div_pow
    set /a kk = %1 - %begin%
    set /a p = %2
    set /a nn = "a_%kk%"
    set /a e = 0
    :loop_div_pow
        set /a r = %nn% %% %p%
        if %r% NEQ 0 (
            set /a a_%kk% = %nn%
            set /a b_%kk% *= %e% + 1
            exit /b 0
        )
        set /a e += 1
        set /a nn /= %p%
        goto :loop_div_pow

:make_primes
    set /a a.size = %2
    call :fill_vector a 1
    set /a k = 2
    :loop_make_primes
        set /a b = "a_%k%"
        if %b% == 0 set /a k += 1 & goto :loop_make_primes
        set /a k2 = %k% * 2
        for /L %%i in (%k2%, %k%, %2) do set /a a_%%i = 0
        set /a k += 1
        set /a k_sq = %k% * %k%
        if %k_sq% LSS %2 goto :loop_make_primes
    
    set /a k = 2
    :loop_make_primes2
        set /a b = "a_%k%"
        if %b% == 1 call :push_vector %1 %k%
        set /a k += 1
        if %k% LSS %2 goto :loop_make_primes2
    exit /b 0

:fill_vector
    set /a max_index = "%1.size" - 1
    for /L %%i in (0, 1, %max_index%) do set /a %1_%%i = %2
    exit /b 0

:print_vector
    setlocal
    set vector=%1
    set /a size = "%vector%.size"
    if %size% == 0 echo %2 & exit /b 0
    set /a e = "%vector%_0"
    set s=%e%
    set /a k = 1
    :loop_print_vector
        if %k% == %size% echo %s% & exit /b 0
        set /a e = "%vector%_%k%"
        set s=%s% %e%
        set /a k += 1
        goto :loop_print_vector

:push_vector
    set /a size = "%1.size"
    set /a %1_%size% = %2
    set /a %1.size = %size% + 1
    exit /b 0

:range
    if "%3" == "" call :range %1 0 %2 1 & exit /b 0
    if "%4" == "" call :range %1 %2 %3 1 & exit /b 0
    
    set /a max_index = (%3 - %2) / %4 - 1
    set /a %1.size = %max_index% + 1
    for /L %%i in (0, 1, %max_index%) do (
        set /a %1_%%i = %2 + %%i * %4
    )
    exit /b 0

:get_time
    setlocal
    set t=%TIME%
    set /a h = %t:~0,2%
    set /a m = 1%t:~3,2% %% 100
    set /a s = 1%t:~6,2% %% 100
    set /a ss = 1%t:~-2% %% 100
    set /a ret = ((%h% * 60 + %m%) * 60 + %s%) * 100 + %ss%
    exit /b %ret%