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

Problem 27

この問題は、パッと見素数判定が大変そうですが、実は判定する数はそんなに大きくはならないのです。だから、必要になったら1000ごとにエラトステネスのふるいをかけて素数を持っておけばよいです。エラトステネスのふるい用に配列で持っておき、それとは別にsetのように持っておいて素数判定します。

set setp_%n% = 1

というように%n%を格納して、

set /a exist = "setp_%n%"

として、%exist%が1ならそのセットに存在するというようにします。
aとbは共に奇数でなければなりません。aを偶数とすると、n² + anはnと偶奇性が同じになるので、n² + an + bはnを1ずつ増加させていくと偶奇が交互に来ることになり、素数が続かないことになります。aが奇数でbが偶数のときは必ず偶数になり、これもダメです。
同様に3の剰余についても考えます。そうすると、aが剰余0のときbは1、それ以外のときはbは2でなければならないことがわかります。これを考えに入れると3倍速くなります。
5以上の素数についても同様に考えることができますが、今回はパスです。
これでもバッチファイルでは2時間くらいかかりそうです。

ちなみに、この答えは結局Eulerの与えた式と本質的に変わらないのですが、10⁵までPythonで計算させても同じでした。それだけEulerの式は特殊だということです。

@echo off

setlocal enabledelayedexpansion
set /a N = 1000
set /a offs = 0
set /a max_length = 0
set /a begin_a = -%N% / 2 * 2 + 1
set /a end_a = %N% - 1
for /L %%a in (%begin_a%, 2, %end_a%) do (
    set /a r_a = %%a %% 3
    if !r_a! == 0 (
        set /a begin_b = 7
    ) else (
        set /a begin_b = 5
    )
    set /a end_b = %N% - 1
    for /L %%b in (!begin_b!, 1, !end_b!) do (
        call :prime_length %%a %%b
        if !ERRORLEVEL! GTR !max_length! (
            set /a max_length = !ERRORLEVEL!
            set /a max_mul = %%a * %%b
        )
    )
)
echo %max_length% %max_mul%
exit /b 0

:prime_length
    set /a nn = 0
    :loop_prime_length
        set /a mm = (%nn% + %1) * %nn% + %2
        call :is_prime %mm%
        if %ERRORLEVEL% == 0 exit /b %nn%
        set /a nn += 1
        goto :loop_prime_length

:is_prime
    if %1 LSS 2 exit /b 0
    
    if %1 LSS %offs% (
        set /a exist = "setp_%1"
        exit /b !exist!
    )
    
    if %offs% == 0 (
        call :sieve p %N%
    ) else (
        call :sieve2 p %N% %offs%
    )
    set /a offs += %N%
    call :is_prime %1
    exit /b %ERRORLEVEL%

:sieve
    set /a max_n = %2 - 1
    call :fill a %2 1
    set /a p = 2
    :loop_sieve
        set /a p_twice = %p% * 2
        for /L %%m in (%p_twice%, %p%, %max_n%) do set /a a_%%m = 0
        set /a p += 1
        set /a p_sq = %p% * %p%
        if %p_sq% LSS %2 goto :loop_sieve
    
    set /a %1.size = 0
    for /L %%n in (2, 1, %max_n%) do (
        set /a b = "a_%%n"
        if !b! == 1 (
            call :push_vector %1 %%n
            set setp_%%n=1
        )
    )
    exit /b 0

:sieve2
    call :fill a %2 1
    set /a offs = %3
    set /a end = %2 + %offs% - 1
    set /a _k = 0
    :loop_sieve2
        set /a p = "p_%_k%"
        set /a p_sq = %p% * %p%
        if %p_sq% GTR %end% goto :sieve2_end
        set /a begin = %offs% + %p% - 1
        set /a begin = %begin% / %p% * %p%
        for /L %%n in (%begin%, %p%, %end%) do (
            set /a _l = %%n - %offs%
            set /a a_!_l! = 0
        )
        set /a _k += 1
        goto :loop_sieve2
    
    :sieve2_end
        set /a max_index = %2 - 1
        for /L %%k in (0, 1, %max_index%) do (
            set /a b = "a_%%k"
            if !b! == 1 (
                set /a _n = %%k + %offs%
                call :push_vector p !_n!
                set setp_!_n!=1
            )
        )
        exit /b 0

:fill
    set /a %1.size = %2
    set /a max_index = %2 - 1
    for /L %%k in (0, 1, %max_index%) do set /a %1_%%k = %3
    exit /b 0

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

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