SHOULD BE WRITTEN WITHE JAVE FORM

Imort.jave.until.Scanner;

Home assignment #1 (Deadline Sunday 21 Feb. 2021) ALGORITHM 2 CICA(m, n) Input: Two non-negative, not-both-zero integers m and n Output: Greatest Common Divisor of m and n te min(m, n) stop false while stop = false do If m mod t = 0 AND n mod t = 0 stop = true; Elsett t-1 1. Code the three algorithms covered in Chapter 1 to solve the Greatest Common Divisor (use long as number types). 2. Provide the running times of the different algorithms using the given instances. 3. Use MS Excel to draw a bar chart diagram illustrating the running times of each problem instance using each algorithm (Similar to the given diagram). Running times of different algorithms 20 10 1.1 Harrath's algorithm 3 for computing gcd(m, n) Step 1 If n = 0, return m, else go to step 2 Step 2 if m= 0, return n, else go to step 3 Step 3 if m divides n return m, else go to step 4 Step 4 if n divides m return n, else go to step 5 Step 5 Find the divisors of m Step 6 Find the divisors of n Step 7 Find the common divisors between m and n Step 8 gcd(m, n) = the greatest common divisor between m and n 0 rti rt2 rt3 Instances 11 12 13 Algorithms ALGORITHM1 Euclid(m, n) Input: Two non-negative, not-both-zero integers m and n Instances Output: Greatest Common Divisor of m and n while n 70 do rem mod n men 1 GCD(m,n) t2 t3 Instance 1 2 3 4 5 71 1250 178208 1458 25825 2x106 25000825 20347796 18497562 99941714720 4x1010