fork download
copy 
  1. ; the prime ant
  2.  
  3. (define (lpf n) ; least prime factor
  4.   (let ((wheel '#(1 2 2 4 2 4 2 4 6 2 6)))
  5.     (let loop ((f 2) (w 0))
  6.       (if (< n (* f f)) n
  7.         (if (zero? (modulo n f)) f
  8.           (loop (+ f (vector-ref wheel w))
  9.                 (if (= w 10) 3 (+ w 1))))))))
  10.  
  11. (define (prime? n) (= (lpf n) n))
  12.  
  13. (define (prime-ant n . verbose?)
  14.   (let ((a (make-vector (+ n 2))))
  15.     (do ((i 0 (+ i 1))) ((= (+ n 2) i))
  16.       (vector-set! a i (+ i 2)))
  17.     (let loop ((n n) (p 0))
  18.       (when (and (pair? verbose?) (equal? (car verbose?) #t))
  19.         (display a) (display " ") (display p) (newline))
  20.       (if (zero? n) p
  21.         (if (prime? (vector-ref a p))
  22.             (loop (- n 1) (+ p 1))
  23.             (let ((q (lpf (vector-ref a p))))
  24.               (vector-set! a p (/ (vector-ref a p) q))
  25.               (vector-set! a (- p 1) (+ (vector-ref a (- p 1)) q))
  26.               (loop (- n 1) (- p 1))))))))
  27.  
  28. (display (prime-ant 47)) (newline)
  29. (display (prime-ant 20 #t)) (newline)
Success #stdin #stdout 0.02s 42832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9
#(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 0
#(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 1
#(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2
#(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 1
#(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2
#(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3
#(2 5 2 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4
#(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3
#(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4
#(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5
#(2 5 2 7 3 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6
#(2 5 2 7 3 9 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5
#(2 5 2 7 6 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4
#(2 5 2 9 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3
#(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 2
#(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 3
#(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 4
#(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5
#(2 5 5 3 3 3 4 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6
#(2 5 5 3 3 5 2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 5
#(2 5 5 3 3 5 2 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23) 6
6
https://ideone.com/dok8t1
language:
Scheme (guile 2.2.4)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!