Unten ist mein Versuch im R5RS-Schema (Haftungsausschluss: Ich bin (noch!) Kein Schemer, also verzeihen Sie den (wahrscheinlich) schrecklichen 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)
Druckt als:
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)
(Nicht genau wie in der Aufgabenbeschreibung, aber alles, was Sie tun müssen, um diese Ausgabe zu erhalten, ist, die Liste zu falten und Wiederholungen derselben Nummer während des Ausgabeteils des Codes zusammenzuführen. Die interne Darstellung / der interne Algorithmus wäre immer noch das Gleiche.)
Die Idee ist, die zuvor berechneten Werte zwischenzuspeichern, aber die Tatsache zu nutzen, dass die Faktoren von n
der erste Primfaktor von n
und die Primfaktoren von (n / erster Faktor) sind. Letzteres ist jedoch bereits bekannt, sodass wir die bereits vorhandene Liste von Faktoren für diese kleinere Anzahl erneut verwenden. Somit wird für jede Zahl, in [1..n]
der es sich nicht um eine Primzahl handelt, eine einzelne Nachteilezelle gespeichert.
Für jede Nummer wird eine einzelne Cons-Zelle erstellt und gespeichert. Daher sollte dieser Ansatz mit der O(n)
Speichernutzung ausgeführt werden. Ich habe keine Ahnung, ob es möglich ist, die zeitliche Komplexität sauber auszudrücken.