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.
 

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'A fully new path to prove Riemann Hypothesis'

For original Zeta function, ζ(s)=1+1/2^s+1/3^s+1/4^s+... =1+e^(-sln2)+e^(-sln3)+e^(-sln4)+... , Re(s)>1 If we regards it as some function got from Laplace transformation, and let this real function be ζ(x), that means L[ζ(x)]=ζ(s), then: ζ(x)=L^-1[ζ(s)]=δ(x)+δ(x-ln2)+δ(x-ln3)+δ(x-ln4)+... , this represents a series of Dirac delta functions at the points of x=0, ln2, ln3, ln4, ... , It may be still difficult to understand what ζ(x) means, but once it is integrated, the truth is clear...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top