結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー Jashinchan
提出日時 2022-09-06 12:26:09
言語 Lua
(LuaJit 2.1.1734355927)
結果
WA  
実行時間 -
コード長 1,428 bytes
コンパイル時間 259 ms
コンパイル使用メモリ 5,248 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-21 13:44:32
合計ジャッジ時間 913 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

function miller_rabin(n, bases)
    d, s = n - 1, 0
    while d % 2 == 0 do
        d = d / 2
        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
        else
            r = 1
            while a ~= n - 1 do
                if r == s then
                    return false
                end
                a = a * a % n
                r = r + 1
            end
        end
    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(string.format("%u", x))
    io.write(" ")
    if is_prime(x) then
        print("1")
    else
        print("0")
    end
end
0