# Greatest common divisor

• MHB
• matqkks
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.

#### matqkks

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?

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.

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