proposition: Theorem prime_between_correct : forall n m : nat, if prime_between n m then exists p : nat, prime p /\ n <= p /\ p <= n + m else forall p : nat, n <= p -> p <= n + m -> ~ prime p.
proof: Proof. intros n m; generalize n; clear n; elim m; clear m; simpl in |- *; auto. intros n; generalize (primeb_correct n); case (primeb n); auto. intros H; exists n; repeat (split; auto with arith). rewrite <- plus_n_O; auto with arith. intros H p H0 H1; replace p with n; auto with arith. intros m Rec n; generalize (primeb_correct n); case (primeb n); auto. intros H; exists n; repeat (split; auto with arith). intros H; generalize (Rec (S n)); case (prime_between (S n) m); auto with arith. simpl in |- *; rewrite <- plus_n_Sm; intros (p, (H1, (H2, H3))); exists p; repeat (split; auto with arith). simpl in |- *; rewrite <- plus_n_Sm; intros H1 p H2; inversion H2; auto with arith. rewrite <- H0; auto. Qed.
imports: Coq(Arith)