This article describes Java's algorithm for solving the greatest common divisor of two non-negative integers. Share it for your reference, as follows:
Code functions:
1. Java implementation (full source code with test cases);
2. Solve the greatest common divisor of two non-negative integers p and q (p>=q);
3. Two solutions: loop method and recursive method;
Complete source code:
/* GCD:Greateast Common Divisor */public class GCD{ public static void main(String args[]){ /* Test Case */ int p = 32; int q = 24; System.out.println("The greatest divisior of "+p+" and "+q+" is /n"+ "[ gcd1 ] : "+gcd1(p,q)+"/n"+"[ gcd2 ] : "+ gcd2(p,q)); } // (q % gcd ==0 AND p% gcd ==0 [gcd from q to 1]) public static int gcd1(int p,int q){ int gcd=1; int d=q; while(d>0){ d--; if(q%d==0 && p%d==0){ gcd = d; break; } } return gcd; } // gcd(p,q)=gcd(q,p%q)[if q=0,gcd=p] public static int gcd2(int p,int q){ if(q==0) return p; int r = p%q; //System.out.println("("+q+","+r+")"); return gcd2(q,r); }}Running screenshot:
Code explanation:
Circular method gcd1(p,q)
Natural language description: Loop method solves the greatest common divisor of two non-negative integers p, q (p>=q), that is, solves the maximum value of the common divisor of q that is p. Let d (divided) decrement from p (decrement step = 1) d is always "the maximum value of the condition that is about to be satisfied". When d meets the condition (it can be divided by p and divisible by p), d is the common divisor of p and q, and d is the greatest common divisor of p and q;
Recursive method gcd2(p,q)
Natural language description: Recursive method solves the greatest common divisor of two non-negative integers p, q (p>=q). When q is equal to 0, the greatest common divisor is p; otherwise, take the remainder of p and q to obtain r=p%q, and the greatest common divisor of p and q is the greatest common divisor of q and r;
Code experience:
Regarding the loop method, at the beginning, what I thought of was to write a method to solve common divisors, use an integer array to store all common divisors of a non-negative integer, and then compare and find out the largest common divisor common in p and q, which is the greatest common divisor of two numbers. Later, I thought, since it is to find the maximum, wouldn’t it be easier to directly decrement from the back to the front? Decreasing from the back to the front can ensure that this number is always the largest at present, because people who are bigger than it do not meet the conditions (can be divided by p and q at the same time) are eliminated, which avoids the trouble of finding the maximum initially. Although there are many ways to find the maximum, if you have or have not needed to prove and search, haha, why do you feel a bit about philosophy?
Regarding recursion, what I can fully understand based on my intuition is the only sentence that the greatest common divisor of p and q is the greatest common divisor of q and r (r=p%q), which is the beginning of the ring, but I still don’t quite understand that the end condition of the ring is 0, and return p;
Although it is a very simple solution to the greatest common divisor algorithm, I have to write it in two ways, mainly to feel the recursion method that I am not very familiar with. In the past, I saw the clear formula of the recursion algorithm for solving the Hannover Tower and Fibonacci numbers that was illuminated there, and I was sighing that this is completely mathematics! The feeling I learned today was even more shocking than that time. I wondered what happened and solved it strangely. At that time, I didn't care much about memory, efficiency and other indicators. I just thought that the guys who could think of this were really smart. For them, whether it was a computer or a programming language, it was just a tool to solve the problem. Some people say that recursion is an algorithm that allows the brain to think about computers to calculate, and it feels really appropriate.
References
Turing Programming Series: Algorithms (4th Edition) Robert Sedgewick (Author), Kevin Wayne (Author), Xie Luyun (Translator)
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.