- This article is not about Euclidean geometry.
In number theory, the Euclidean algorithm (also called Euclid's algorithm) is an algorithm to determine the greatest common divisor (GCD) of two integers or elements of any Euclidean ___domain (for example, polynomials over a field) by repeatedly dividing the two numbers and the remainder in turns. Its major significance is that it does not require factoring the two integers, and it is also significant in that it is one of the oldest algorithms known, dating back to the ancient Greeks.
History of the Euclidean algorithm
The Euclidean algorithm is one of the oldest algorithms known, since it appeared in Euclid's Elements around 300 BC. Euclid originally formulated the problem geometrically, as the problem of finding a common "measure" for two line lengths, and his algorithm proceeded by repeated subtraction of the shorter from the longer segment. However, the algorithm was probably not discovered by Euclid and it may have been known up to 200 years earlier. It was almost certainly known by Eudoxus of Cnidus (about 375 BC); and Aristotle (about 330 BC) hinted at it in his Topics, 158b, 29-35.
this boring and i dont like to do this on my course
This is boring i hate this stuff lol
boring boring broing lol
boring lol
boring
ummmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm boring
PHP/JavaScript implementation
PHP
function gcd($a, $b) {
if ($b == 0) return $a;
else return gcd($b, $a % $b);
}
JavaScript
function gcd(var a, var b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
See also
References
- Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89684-2. Sections 4.5.2–4.5.3, pp.333–379.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.2: Greatest common divisor, pp.856–862.