题目地址

https://ac.nowcoder.com/acm/contest/57677/A

代码

use std::io::{self, BufRead, Write};

fn is_prime_triival(n: i128) -> bool {
    if n <= 1 {
        return false;
    }
    if n == 2 {
        return true;
    }
    if n % 2 == 0 {
        return false;
    }
    let mut i = 3;
    while (i as f64) <= (n as f64).sqrt() {
        if n % i == 0 {
            return false;
        }
        i += 2;
    }
    true
}


fn power(mut a: i128, mut b: i128, m: i128) -> i128 {
    let mut result = 1;
    a %= m;
    while b > 0 {
        if b % 2 != 0 {
            result = (result * a) % m;
        }
        b >>= 1;
        a = (a * a) % m;
    }
    result
}

fn is_prime(n: i128) -> bool {
    if n < 2 {
        return false;
    }
    if n != 2 && n % 2 == 0 {
        return false;
    }
    let s = ((n - 1) as u128).trailing_zeros() as i128;
    let d = (n - 1) / 2i128.pow(s as u32);

    let witnesses: [i128; 12] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37];
    'next_witness: for &a in witnesses.iter().take_while(|&&x| x <= n - 1) {
        let mut x = power(a, d, n);
        if x == 1 || x == n - 1 {
            continue;
        }
        for _r in 1..s {
            x = power(x, 2, n);
            if x == n - 1 {
                continue 'next_witness;
            }
        }
        return false;
    }
    true
}





fn solve(_n: i128) -> i128 {
    if _n == 1 {
        return 1;
    } else if _n == 4 {
        return 4;
    } else {
        let mut n = _n;
        while !is_prime(n) {
            n -= 1;
        }
        return n;
    }
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let t: i32 = lines.next().unwrap().unwrap().trim().parse().unwrap();

    let stdout = io::stdout();
    let mut writer = io::BufWriter::new(stdout.lock());
    for _ in 0..t {
        let n: i128 = lines.next().unwrap().unwrap().trim().parse().unwrap();
//         println!("n {}", is_prime(n));
        let result = solve(n);
        writeln!(&mut writer, "{}", result).unwrap();
    }
}