Until the remaining length r in R is less than the shorter length s in S, repeatedly subtract the measuring number s in S from the remaining length r in R. IF S > R THEN done measuring so GOTO 10 ELSE measure again, R ← R − S [Remainder-loop]: GOTO 7. E2: [Is the remainder zero?]: EITHER (i) the last measure was exact, the remainder in R is zero, and the program can halt, OR (ii) the algorithm must continue: the last measure left a remainder in R less than measuring number in S. IF R = 0 THEN done so GOTO step 15 ELSE CONTINUE TO step 11, E3: [Interchange s and r]: The nut of Euclid's algorithm. Use remainder r to measure what was previously smaller number s; L serves as a temporary location. L ← R R ← S S ← L [Repeat the measuring process]: GOTO 7 OUTPUT: [Done. S contains the greatest common divisor]: PRINT S DONE: HALT, END, STOP. An elegant program for Euclid's algorithm The flowchart of "Elegant" can be found at the top of this article. In the (unstructured) Basic language, the steps are numbered, and the instruction LET [] = [] is the assignment instruction symbolized by ←. 5 REM Euclid's algorithm for greatest common divisor 6 PRINT "Type two integers greater than 0" 10 INPUT A,B 20 IF B=0 THEN GOTO 80 30 IF A > B THEN GOTO 60 40 LET B=B-A 50 GOTO 20 60 LET A=A-B 70 GOTO 20 80 PRINT A 90 END How "Elegant" works: In place of an outer "Euclid loop", "Elegant" shifts back and forth between two "co-loops", an A > B loop that computes A ← A − B, and a B ≤ A loop that computes B ← B − A. This works because, when at last the minuend M is less than or equal to the subtrahend S (Difference = Minuend − Subtrahend), the minuend can become s (the new measuring length) and the subtrahend can become the new r (the length to be measured); in other words the "sense" of the subtraction reverses. The following version can be used with programming languages from the C-family: // Euclid's algorithm for greatest common divisor int euclidAlgorithm (int A, int B) { A = abs(A); B = abs(B); while (B != 0) { while (A > B) { A = A-B;