fact: Definition prime_test (n:nat) : bool := match n with | 0%nat => false | 1%nat => false | S (S n) => let x := (Z_of_nat (S (S n))) in let s := (Z.sqrt x) in let (half_s, even_bit) := match s with | Zpos(xI h) => (Zpos h, 0) | Zpos(xO h) => (Zpos h, 1) | Zpos xH => (0, 0) | _ => (0, 1) end in test_odds (Z.abs_nat half_s) (s + even_bit) x end.
imports: ZArith Arith Bool Lia