Question: Several algorithms exist for solving for the greatest common denominator of 2 positive integers. One algorithm is the Consecutive Integer Checking algorithm, which summarized in
Several algorithms exist for solving for the greatest common denominator of 2 positive integers. One algorithm is the Consecutive Integer Checking algorithm, which summarized in slide 4. Another algorithm for computing the GCD is Euclid's alorithm, which is summarized in slide 3. Your task this project is to implement these algorithms using the starting code provided (comments delimit the areas you should complete). Your code must do the following:
Steps
- Read in the 2 integers given in the format shown below.
- Check to ensure both integers are non-negative and at least 1 integer is positive (pre-conditions). If true, go to step 3. If false, go to step 6.
- Calculate the GCD and the number of iterations required to obtain the GCD for the Consecutive Integer Checking algorithm. Output these in the format shown below as 1 line.
- Calculate the GCD and the number of iterations required to obtain the GCD for Euclid's algorithm. Output these in the format shown below as the second line.
- Exit the program. Don't do step 6.
- Output the message Invalid input.
The input and output must match the specified Input and Output exactly. Several test cases are shown below, but other test cases must be run in the project that are not shown in this description. Run all the test cases then submit ir on Replit.
Input
The input consists of 1 line with 2 integers, m and n, separated by a space. The integers may be any value in the range -1000000 <= m, n <= 1000000.
Output
The output must be either 2 lines with the GCD and number of iterations for the 2 algorighms as described above, or 1 line saying Invalid input.
import java.util.Scanner;
class Main {
private int numConsecutive = 0; // Counter for consecutive integer algorithm
private int numEuclid = 0; // Counter for Euclid algorithm
public static void main(String[] args) {
Main obj = new Main(); // Instantiate an object of type Main
obj.run(); // Call the run() method which does all the hard work
}
/**
run() in an instance method that performs the main work
**/
public void run() {
// Step 1
Scanner kb = new Scanner(System.in);
int m = kb.nextInt();
int n = kb.nextInt();
int gcd = 0;
// Close the Scanner resource
kb.close();
// Step 2
if(numbersValid(m, n)) {
gcd = conIntCheck(m, n);
System.out.printf("%d %d ", gcd, numConsecutive);
gcd = euclid(m, n);
System.out.printf("%d %d ", gcd, numEuclid);
}
else {
System.out.println("Invalid input");
}
}
/**
Returns a boolean - true if the 2 numbers are in range and false if not
**/
private boolean numbersValid(int m, int n) {
boolean valid = false;
// TO DO
return valid;
}
/**
Consecutive Integer Check algorithm - Decrease by 1!!!
**/
private int conIntCheck(int m, int n) {
int res = 0;
int t = ; // TO DO
while(// TO DO) {
numConsecutive++;
// TO DO
}
return res;
}
/**
Euclid's algorithm
**/
private int euclid(int m, int n) {
int r = 0;
while(// TO DO) {
numEuclid++;
// TO DO
}
return m;
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help