Greatest common divisor

In summary, the main advantage of using Euclid's algorithm over prime decomposition to find the gcd of two numbers is that it is computationally cheaper and takes a negligible amount of effort. Therefore, it is recommended to use Euclid's algorithm in most cases, unless prime decomposition is specifically needed for other purposes.
  • #1
285
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
  • #2
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.
 

Similar threads

  • General Math
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
886
Replies
6
Views
762
Replies
19
Views
4K
Replies
17
Views
2K
Replies
4
Views
1K
Replies
1
Views
1K
Replies
8
Views
1K
  • General Math
Replies
11
Views
5K
Replies
4
Views
2K
Back
Top