DO ALL PARTS

3. The following algorithm CountMultiples, takes as input a list of m 1 distinct positive integers and returns the number of list elements that are a multiple of some prior list element. For example, on the input 2,6, 5, 9, 8, 3, 15, the algorithm would return 3 because there are 3 list elements that are a multiple of some prior list element 6 is a multiple of 2 8 is a multiple of 2 15 is a multiple of 5 (and it is a multiple of 3) procedure Count Multiples (a1 an: n 1) 1. if n 1 then return 0 2. count 0 3. m Count Multiples (a1, an-1) 4. for 1 to n -1 5. f a divides an then return. m 1 6. return m (a) Prove that CountMultiples is correct. Proof: We can prove that tiples is correct for any input of size n, using strong weak regular induction on n. For the base case, when n 1, Count Multiples returns 0 in line 1. This is correct because Now suppose as the inductive hypothesis that CountMultiples is correct on all inputs of size and we will show that it is correct on all inputs of size n, where n 1. Let a1, an be an arbitrary input of size n