結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー Jashinchan
提出日時 2022-09-06 11:58:48
言語 Lua
(LuaJit 2.1.1787165859)
コンパイル:
luajit -b _filename_ a.out
実行:
luajit _filename_
結果
TLE  
実行時間 -
コード長 1,409 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 53 ms
コンパイル使用メモリ 9,872 KB
実行使用メモリ 9,860 KB
最終ジャッジ日時 2026-09-27 13:22:15
合計ジャッジ時間 14,379 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

function pow_mod(a, k, m)
    ret = 1
    b = a
    deg = k
    while deg > 0 do
        if deg & 1 == 1 then
            ret = ret * b % m
        end
        b = b * b % m
        deg = deg >> 1
    end
    return ret
end

function miller_rabin(n, bases)
    d, s = n - 1, 0
    while d % 2 == 0 do
        d = d >> 1
        s = s + 1
    end
    for i, base in ipairs(bases) do
        if n <= base then
            return true
        end
        a = pow_mod(base, d, n)
        if a == 1 then
            goto continue
        end
        r = 1
        while a ~= n - 1 do
            if r == s then
                return false
            end
            a = a * a % n
            r = r + 1
        end
        ::continue::
    end
    return true
end

function is_prime(n)
    if n <= 1 then
        return false
    end
    if n == 2 or n == 3 or n == 5 or n == 7 then
        return true
    end
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 then
        return false
    end
    if n < 121 then
        return true
    end
    if n < 4759123141 then
        return miller_rabin(n, {2, 7, 61})
    end
    return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022})
end

local n = io.read("*n")

while n > 0 do
    n = n - 1
    local x = io.read("*n")
    io.write(x)
    io.write(" ")
    if is_prime(x) then
        print("1")
    else
        print("0")
    end
end
0