use rug::{rand::RandState, Complete, Integer};
use std::io;

fn rabin_miller_test(n: &Integer, k: u32) -> bool {
    let one = Integer::from(1u32);
    let two = Integer::from(2u32);
    let n1 = Integer::from(n - 1u32);

    let mut s = 0;
    let mut d = n1.clone();
    while d.mod_u(2u32) == 0 {
        s += 1u32;
        d /= 2u32;
    }

    let mut rand = RandState::new();

    'outer: for _ in 0..k {
        let bound = n.clone() - 4u32;
        let a = bound.random_below(&mut rand) + 2u32;
        let mut x = Integer::from(a.pow_mod_ref(&d, n).unwrap());
        if x == one || x == n1 {
            continue;
        } else {
            for _ in 0..=s - 1 {
                x = Integer::from(x.pow_mod_ref(&two, n).unwrap());
                if x == one {
                    return false;
                } else if x == n1 {
                    continue 'outer;
                }
            }
        }
        return false;
    }
    return true;
}

fn main() {
    println!("Введите положительное нечётное число n:");
    let mut p = String::new();
    let stdin = io::stdin();
    match stdin.read_line(&mut p) {
        Ok(_) => (),
        Err(_) => {
            println!("Произошла ошибка при чтении из стандартного ввода");
            return ();
        }
    }
    let p = match Integer::parse(p) {
        Ok(parsed) => parsed.complete(),
        Err(_) => {
            println!("Не удалось считать число");
            return ();
        }
    };
    if p.is_divisible(&Integer::from(2u32)) {
        println!("Введено чётное число");
        return ();
    }

    println!("Введите количество раундов k:");
    let mut k = String::new();
    match stdin.read_line(&mut k) {
        Ok(_) => (),
        Err(_) => {
            println!("Произошла ошибка при чтении из стандартного ввода");
            return ();
        }
    }
    let k = match k.trim_end().parse::<u32>() {
        Ok(parsed) => parsed,
        Err(_) => {
            println!("Не удалось считать число");
            return ();
        }
    };

    let is_prime = rabin_miller_test(&p, k);
    if is_prime {
        let probability = 1f64 - 0.25f64.powf(k as f64);
        println!(
            "Число {} является простым с вероятностью {}",
            &p, probability
        );
    } else {
        println!("Число не является простым");
    }
}