Skip to main content

miller_rabin

competitive::math::miller_rabin

Function miller_rabin 

Source 
pub fn miller_rabin(n: u64) -> bool
Examples found in repository?
crates/library_checker/src/number_theory/primality_test.rs (line 10)
5pub fn primality_test(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(q);
8    for _ in 0..q {
9        sc!(n: u64);
10        let ans = if miller_rabin(n) { "Yes" } else { "No" };
11        pp!(ans);
12    }
13}
More examples
Hide additional examples
crates/competitive/src/math/fast_prime_mod.rs (line 52)
45    pub fn new() -> Self {
46        assert!(
47            BUILD_INV || BUILD_POW,
48            "at least one of BUILD_INV or BUILD_POW must be true"
49        );
50        assert!(P < 1 << 30, "P must be less than 2^30");
51        assert!(
52            P % 2 == 1 && miller_rabin(P as u64),
53            "P must be an odd prime"
54        );
55
56        let (root, pow_lo, pow_hi, log) = if BUILD_POW {
57            let root = if P == 998_244_353 {
58                3
59            } else {
60                primitive_root(P as u64) as u32
61            };
62            let (pow_lo, pow_hi) = build_pow::<P>(root);
63            let log = build_log::<P>(root, &pow_lo, &pow_hi);
64            (root, pow_lo, pow_hi, log)
65        } else {
66            (
67                0,
68                Vec::new().into_boxed_slice(),
69                Vec::new().into_boxed_slice(),
70                Vec::new().into_boxed_slice(),
71            )
72        };
73        let inv = if BUILD_INV {
74            build_inv::<P>()
75        } else {
76            Vec::new().into_boxed_slice()
77        };
78        let frac = if is_direct_table_mod::<P>() {
79            Vec::new().into_boxed_slice()
80        } else {
81            build_frac::<P>()
82        };
83        Self {
84            root,
85            pow_lo,
86            pow_hi,
87            frac,
88            log,
89            inv,
90        }
91    }