mirror of
https://github.com/ashinn/chibi-scheme.git
synced 2025-05-19 05:39:18 +02:00
12 lines
524 B
Scheme
12 lines
524 B
Scheme
(define (totient n)
|
|
(let ((limit (exact (ceiling (sqrt n)))))
|
|
(let lp ((i 2) (count 1))
|
|
(cond ((> i limit)
|
|
(if (= count (- i 1))
|
|
(- n 1) ; shortcut for prime
|
|
(let lp ((i i) (count count))
|
|
(cond ((>= i n) count)
|
|
((= 1 (gcd n i)) (lp (+ i 1) (+ count 1)))
|
|
(else (lp (+ i 1) count))))))
|
|
((= 1 (gcd n i)) (lp (+ i 1) (+ count 1)))
|
|
(else (lp (+ i 1) count))))))
|