ATestforPrimalityisthefollowing:
Given an integer n > 1, to test whether n is prime check tosee if it is divisible by a prime number less than or equal to it’ssquare root. If it is not divisible by an of these numbers then itis prime.
We will show that this is a valid test.
- prove
∀n, r, s ∈ N+, r s ≤ n → (r ≤ √n ∨ s ≤ √n)
b) Prove ∀ n ∈ N+ , n is not prime →∃p ∈ N ,(p prime ∧ (p≤√n) ∧p∣n )
(c) State the contrapositive of the statement of part(b).
