結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー JashinchanJashinchan
提出日時 2022-09-06 12:11:32
言語 Lua
(LuaJit 2.1.1696795921)
結果
WA  
実行時間 -
コード長 1,407 bytes
コンパイル時間 55 ms
コンパイル使用メモリ 6,944 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-21 13:33:02
合計ジャッジ時間 645 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

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(x)
    io.write(" ")
    if is_prime(x) then
        print("1")
    else
        print("0")
    end
end
0