A continuación se muestra mi intento, en el esquema R5RS (descargo de responsabilidad: en realidad no soy un Schemer (¡todavía!), Así que perdón por el (probablemente) terrible código).
(define count 10)
; `factors` is our vector of linked-lists of factors. We're adding to these
; as we go on.
(define factors (make-vector count 'not-found))
(vector-set! factors 0 '())
; `primes-so-far` contains all the prime numbers we've discovered thus far.
; We use this list to speed up the dividing of numbers.
; `primes-so-far-last` is a ref to the last entry in the `primes-so-far`
; list, for O(1) appending to the list.
(define primes-so-far '(dummy))
(define primes-so-far-last primes-so-far)
;; Helpers
(define (factor-ref n)
(vector-ref factors (- n 1)))
(define (factor-cached? n)
(not (eq? (vector-ref factors (- n 1)) 'not-found)))
(define (factor-put n factor)
(let* ((rest (/ n factor))
(factor-cell (cons factor (factor-ref rest))))
(vector-set! factors (- n 1) factor-cell)
factor-cell))
(define (prime-append n)
(let ((new-prime-cell (cons n '())))
(set-cdr! primes-so-far-last new-prime-cell)
(set! primes-so-far-last new-prime-cell)
new-prime-cell))
;; The factor procedure (assumes that `[1..n-1]` have already been factorized).
(define (factor n)
(define (divides? m n)
(= (modulo n m) 0))
; n the number to factor.
; primes the list of primes to try to divide with.
(define (iter n primes)
(cond ((factor-cached? n)
(factor-ref n))
((null? primes)
; no primes left to divide with; n is prime.
(prime-append n)
(factor-put n n)) ; the only prime factor in a prime is itself
((divides? (car primes) n)
(factor-put n (car primes))
(factor-ref n))
(else
(iter n (cdr primes)))))
(iter n (cdr primes-so-far)))
(define (print-loop i)
(if (<= i count)
(begin
(display i)
(display ": ")
(display (factor i))
(newline)
(print-loop (+ i 1)))))
(print-loop 1)
Imprime como:
1: ()
2: (2)
3: (3)
4: (2 2)
5: (5)
6: (2 3)
7: (7)
8: (2 2 2)
9: (3 3)
10: (2 5)
(No exactamente como en la descripción de la tarea, pero todo lo que tendría que hacer para obtener esa salida es doblar la lista y fusionar las repeticiones del mismo número, durante la parte de salida del código. La representación / algoritmo interno aún sería lo mismo.)
La idea es almacenar en caché los valores calculados anteriormente, pero hacer uso del hecho de que los factores de n
es el primer factor primo de n
y los factores primos de (n / primer factor). Pero esto último ya se conoce, por lo que simplemente reutilizamos la lista de factores ya existente para ese número menor. Por lo tanto, para cada número en el [1..n]
que no es primo, se almacena una sola celda de contras.
Para cada número, se crea y almacena una sola celda de contras. Por lo tanto, este enfoque debe ejecutarse con O(n)
el uso del almacenamiento. No tengo idea de si es posible expresar perfectamente la complejidad del tiempo.