; prime partitions

(define (prime-parts n)
  (let ((sopf (make-vector (+ n 1) 0))
        (kappa (make-vector (+ n 1) 0)))
    (vector-set! sopf 0 1)
    (vector-set! kappa 0 1)
    (do ((p 2 (+ p 1))) ((< n p))
      (when (zero? (vector-ref sopf p))
        (do ((i p (+ i p))) ((< n i))
          (vector-set! sopf i
            (+ (vector-ref sopf i) p)))))
    (do ((i 2 (+ i 1)))
        ((< n i) (vector-ref kappa n))
      (vector-set! kappa i
        (do ((j 1 (+ j 1))
             (s (vector-ref sopf i)
                (+ s (* (vector-ref sopf j)
                        (vector-ref kappa (- i j))))))
            ((= i j) (/ s i)))))))

(time (begin (display (prime-parts 1000)) (newline)))

48278613741845757
cpu time: 110 real time: 754 gc time: 40