Di bawah ini adalah usaha saya, dalam skema R5RS (disclaimer: Saya sebenarnya bukan Schemer (belum!), Jadi maafkan kode (mungkin) yang mengerikan).
(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)
Mencetak sebagai:
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)
(Tidak persis seperti dalam deskripsi tugas, tetapi yang harus Anda lakukan untuk mendapatkan output adalah melipat daftar dan menggabungkan pengulangan dari nomor yang sama, selama bagian output dari kode. Representasi / algoritma internal masih akan menjadi sama.)
Idenya adalah untuk menembolok nilai yang dihitung sebelumnya, tetapi menggunakan fakta bahwa faktor n
adalah faktor prima pertama n
dan faktor prima (n / faktor pertama). Tetapi yang terakhir sudah diketahui, jadi kami hanya menggunakan kembali daftar faktor yang sudah ada untuk jumlah yang lebih kecil. Jadi, untuk setiap angka [1..n]
yang tidak prima, satu sel kontra tunggal disimpan.
Untuk setiap nomor, satu sel kontra dibuat dan disimpan. Dengan demikian, pendekatan ini harus dijalankan dengan O(n)
penggunaan penyimpanan. Saya tidak tahu apakah mungkin untuk mengekspresikan kompleksitas waktu dengan rapi.