素因数分解するやつ

prime-fact.rkt

#lang racket
(require rackunit)

;; factor x y
;;
;; 割りきれるとき    ->引き数と割った後の数 
;; 割りきれないとき  ->空リストを返す

(define (factor x y) 
  (if (= 0 (modulo x y)) 
      (list y (/ x y))
      '()))

(check-equal? (factor 10 9) '())
(check-equal? (factor 10 5) '(5 2))

;; range-root x
;;
;; root x 以下までのリストを作成する
(define (range-root x)
  (range 2 (+ (floor (sqrt x)) 1)))

(check-equal? (range-root 9) '(2 3))

;; filter-prime-p xs ys
;; 素数だけのリストを生成する
(define (filter-prime-p xs ys)
  (if (null? xs) (reverse ys)
      (let ([x (car xs)]
            [next-xs (cdr xs)])
        (filter-prime-p (filter 
                         (lambda (y) (not (= (modulo y x) 0))) next-xs)
                        (list* x ys)))))

(check-equal? (filter-prime-p (range 2 10) '()) '(2 3 5 7))

;; filter-prime xs
(define (filter-prime xs)
  (filter-prime-p xs '()))

;; prime-factorization-p x y
;; 再帰的に約数をリスト化する
(define (prime-factorization-p x y z)
  (if (null? y) (list* x z)
      (let ([y2 (car y)])
        (cond 
          [(= x 1) z]
          [(= 0 (modulo x y2)) (prime-factorization-p (/ x y2) y (list* y2 z))]
          [else (prime-factorization-p x (cdr y) z)]))))

(check-equal? (prime-factorization-p 4 '(2) '()) '(2 2))
(check-equal? (prime-factorization-p 10 '(2 3) '()) '(5 2))

;; dubricate-count-p x c yz
;; 複数あるものをカウントする

(define (dubricates-count-p x c ys zs)
  (if (null? ys) (append zs (list (list x c)))
      (let ([y (car ys)]
            [next-ys (cdr ys)])
        (if (= x y)
            (dubricates-count-p x (+ c 1) next-ys zs)
            (dubricates-count-p (car ys) 1 next-ys (append zs (list (list x c))))))))

(check-equal? (dubricates-count-p 2 0 '(2 2 5 5) '()) '((2 2) (5 2)))

;; dubricates-count x
;; 上記関数のラップ版
(define (dubricates-count xs)
  (dubricates-count-p (car xs) 1 (cdr xs) '()))

(check-equal? (dubricates-count '(3)) '((3 1)))

;; prime-factorization
;; 上記関数のラップ版

(define (prime-factorization-list x)
  (dubricates-count 
   (reverse
    (prime-factorization-p x (filter-prime (range-root x)) '()))))

(check-equal? (prime-factorization-list 10) '((2 1) (5 1)))

;; fact-pair->string x
(define (fact-pair->string xs)
  (let ([x (car xs)]
        [y (cadr xs)])
    (if (= y 1)
        (number->string x)
        (string-join (map number->string xs) "^"))))

;; prime-factorization-print
(define (prime-factorization-print x)
        (string-join
         (list
          (number->string x)
          " = "
          (string-join (map fact-pair->string (prime-factorization-list x)) " * "))))