Greatest common divisor: Difference between revisions

=={{header|Racket}}==

Racket provides a built-in gcd function. Here's a program that computes the gcd of 14 and 63:

<lang Racket>#lang racket

(gcd 14 63)</lang>

Here's an explicit implementation. Note that since Racket is tail-calling, the memory behavior of this program is "loop-like", in the sense that this program will consume no more memory than a loop-based implementation.

<lang Racket>#lang racket

;; given two nonnegative integers, produces their greatest

;; common divisor using Euclid's algorithm

(define (gcd a b)

(if (= b 0)

a

(gcd b (modulo a b))))

;; some test cases!

(module+ test

(require rackunit)

(check-equal? (gcd (* 2 3 3 7 7)

(* 3 3 7 11))

(* 3 3 7))

(check-equal? (gcd 0 14) 14)

(check-equal? (gcd 13 0) 13))</lang>