The Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor of two integers, the largest number that divides both of them with no remainder, by repeatedly replacing the larger number with the remainder of dividing it by the smaller until a remainder of zero is reached. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements, around 300 BC, making it among the oldest algorithms still in common use today.
Facts
Time Complexity
Time Complexity (category)Logarithmic Time -- O(log n) 1 Classification
Design Technique Connections
In Field
Source Wikipedia: Euclidean Algorithm
Uses Design Technique
Sources
1. Euclidean Algorithm (Wikipedia)
Wikipedia infobox: time complexity logarithmic
logarithmic
Wikipedia: design technique divide-and-conquer
divide-and-conquer
View the Source2. Wikipedia: Euclidean Algorithm
Wikimedia FoundationLead section
named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC)
- In Field: Algorithms and Complexity Theory, Lead paragraph
View the Source Wikidata: Euclidean Algorithm
Wikidata Q230848, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.