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

Click For 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
282
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.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Undergrad How to evaluate the Greatest Common Divisor?
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
2K
MHB Understanding RSA Encryption: What Stops Attackers from Calculating d?
  • · Replies 8 ·
Replies
8
Views
3K
MHB Finding the Greatest EVEN Factor of X: Solving the GCD of m,n=2
  • · Replies 19 ·
Replies
19
Views
5K
What is the Greatest Common Divisor of Two Polynomials?
  • · Replies 3 ·
Replies
3
Views
2K
Is Euclid's Fourth Postulate Redundant?
  • · Replies 3 ·
Replies
3
Views
3K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Undergrad Don't understand lemma about primitive polynomial product
  • · Replies 8 ·
Replies
8
Views
2K
MHB Prove that CnXCm isomorphic to Cgcd(m,n)XClcm(m,n)
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Gradient descent algorithm and optimizers
  • · Replies 5 ·
Replies
5
Views
2K