; prime anagrams
(define (fold-right op base xs)
(if (null? xs)
base
(op (car xs) (fold-right op base (cdr xs)))))
(define (primes n) ; list of primes not exceeding n
(let* ((len (quotient (- n 1) 2)) (bits (make-vector len #t)))
(let loop ((i 0) (p 3) (ps (list 2)))
(cond ((< n (* p p))
(do ((i i (+ i 1)) (p p (+ p 2))
(ps ps (if (vector-ref bits i) (cons p ps) ps)))
((= i len) (reverse ps))))
((vector-ref bits i)
(do ((j (+ (* 2 i i) (* 6 i) 3) (+ j p)))
((<= len j) (loop (+ i 1) (+ p 2) (cons p ps)))
(vector-set! bits j #f)))
(else (loop (+ i 1) (+ p 2) ps))))))
(define ps (list->vector (primes 1620)))
(define (signature str)
(fold-right (lambda (c n)
(modulo (* (vector-ref ps (char->integer c)) n)
(- (expt 2 31) 1)))
1
(string->list str)))
(define (anagram? str1 str2)
(= (signature str1) (signature str2)))
(display (anagram? "time" "emit"))