#747709 (Rust) No.3030 ミラー・ラビン素数判定法のテスト

• 問題: No.3030 ミラー・ラビン素数判定法のテスト
• ユーザー: 👑 zeronosu77108
• 提出日時: 2022-03-23 14:47:26
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 401 ms / 9,973 ms
• コード長: 2,536 bytes
• コンパイル時間: 16,737 ms
• コンパイル使用メモリ: 393,092 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-28 09:49:54
• 合計ジャッジ時間: 18,016 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	215 ms; 5,376 KB
testcase_05	AC	203 ms; 5,376 KB
testcase_06	AC	65 ms; 5,376 KB
testcase_07	AC	63 ms; 5,376 KB
testcase_08	AC	64 ms; 5,376 KB
testcase_09	AC	401 ms; 5,376 KB

ソースコード

fn main() {
    let n : usize = input();
    for _ in 0..n {
        let x : usize = input();
        println!("{} {}", x, if miller_rabin(x as u128) {1} else {0});
    }
}

type MT = u128; fn miller_rabin(n : MT) -> bool { const P: [MT; 12] = [2,3,5,7,11,13,17,19,23,29,31,37]; let pow = |mut x:MT, mut n:MT, m:MT| { let mut res = 1; x %= m; while n != 0 { if n%2==1 { res *= x; res %= m; } x *= x; x %= m; n /= 2; } res }; if P.contains(&n) { return true; } if n <= 1 || n % 2 == 0 { return false; } let mut d = n - 1; while d % 2 == 0 { d /= 2; } for &p in P.iter() { let mut t = d; let mut y = pow(p, t, n); while t!=n-1 && y!=1 && y!=n-1 { y *= y; y %= n; t *= 2; } if y!=n-1 && t%2==0 { return false; } } true }#[allow(dead_code)] fn input<T: std::str::FromStr>() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } #[allow(dead_code)] fn input_t<T: std::str::FromStr, U: std::str::FromStr>() -> (T, U) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t3<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr>() -> (T1, T2, T3) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t4<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr>() -> (T1, T2, T3, T4) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap()) } #[allow(dead_code)] fn input_t5<T1: std::str::FromStr, T2: std::str::FromStr, T3: std::str::FromStr, T4: std::str::FromStr, T5: std::str::FromStr>() -> (T1, T2, T3, T4, T5) { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); let s = s.trim().split_whitespace().collect::<Vec<&str>>(); (s[0].parse().ok().unwrap(), s[1].parse().ok().unwrap(), s[2].parse().ok().unwrap(), s[3].parse().ok().unwrap(), s[4].parse().ok().unwrap()) } #[allow(dead_code)] fn input_vec<T: std::str::FromStr>() -> Vec<T> { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().split_whitespace().map(|s| s.parse().ok().unwrap()).collect() }