1 of 2

Below is my attempt, in R5RS scheme (disclaimer: I'm not actually a Schemer (yet!), so pardon for the (probably) terrible code).

(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)


Prints as:

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)


(Not exactly like in the task description, but all you'd have to do to get that output is to fold the list and merge repetitions of the same number, during the output part of the code. The internal representation/algorithm would still be the same.)

The idea is to cache the previously computed values, but make use of the fact that the factors of n is the first prime factor of n and the prime factors of (n / first-factor). But the latter is already known, so we just re-use the already existing list of factors for that smaller number. Thus, for each number in [1..n] which is not prime, a single cons cell is stored.

For each number, a single cons cell is created and stored. Thus, this approach should run with O(n) storage usage. I've no clue if it's possible to neatly express the time-complexity.