MHB Why Choose Euclid's Algorithm Over Prime Decomposition for Calculating GCD?

AI Thread Summary
Euclid's algorithm is favored for calculating the greatest common divisor (GCD) due to its computational efficiency compared to prime decomposition. While prime decomposition is more complex and resource-intensive, it is only beneficial when required for other calculations. In most cases, Euclid's algorithm can be executed with minimal effort, making it a practical choice. The discussion suggests that Euclid's algorithm should be the primary method for finding GCD unless specific circumstances necessitate prime decomposition. Overall, Euclid's algorithm is the preferred approach for its simplicity and effectiveness.
matqkks
Messages
280
Reaction score
5
What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?
 
Mathematics news on Phys.org
matqkks said:
What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers?
Should you use Euclid’s algorithm in some cases and prime decomposition in others?

Euclid's algorithm is computationally cheaper than prime decomposition.
Prime decomposition is computationally hard, so the only reason to do it, is if the prime decomposition is needed for something else.
In comparison Euclid's algorithm takes a negligible amount of effort. So it can basically be done for free even if prime decomposition is needed for something else.
 
Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
Back
Top