prime-factorization-test.lisp

;; -*- mode: lisp; coding: utf-8 -*-

;; --------------------------------------------------------------------------------
;; 問題：
;; 　210 = 2×3×5×7
;; 整数を素因数分解したとき、上のような、元の数の「各桁の和」と
;; 素因数分解した「×の個数」が等しくなる整数を求めるプログラムを
;; 書いてください
;; https://codeiq.jp/ace/joboffer_apli/q1237?dspn=RHuDm3lalVgWKiDtlJz7oTn0beWgAuPxV4vDWcWiBCBKvMnuVBMQcJTdHL8vKXSh
;; --------------------------------------------------------------------------------

;; 素因数分解する
;; @param number 素因数分解する数
;; @return 素因数分解結果の数値のリスト
;; @example (prime-factorization 120) ;=> (5 3 2 2 2)
(defun prime-factorization (number &optional (i 2) primes)
  (cond
   ((< number i) primes)
   ((= (mod number i) 0)
    (push i primes)
    (prime-factorization (/ number i) i primes))
   (t (prime-factorization number (+ i 1) primes))))

;; 素因数分解した素因数のリストをまとめる
;; @param numbers まとめる対象のリスト
;; @return まとめた結果のリスト（各要素は(素因数 . 個数) のconsセル）
;; @example (compaction '(5 3 2 2 2)) ;=> ((2 . 3) (3 . 1) (5 . 1))
(defun compaction (numbers &optional result)
  (cond
   ((null numbers) result)
   ((and (not (null result)) (= (car (car result)) (car numbers)))
    (incf (cdr (car result)))
    (compaction (cdr numbers) result))
   (t (push (cons (car numbers) 1) result) (compaction (cdr numbers) result))))

;; 数字の各桁の和を求める
;; @param number 対象の数値
;; @return 各桁の和
;; @example (sum-digits 210) ;=> 3
(defun sum-digits (number)
  (do ((n 0))
      ((<= number 0) n)
    (let ((q (floor (/ number 10))))
      (incf n (- number (* q 10)))
      (setf number q))))

;; メイン関数
;; 2～引数limitの値まで因数分解し、各桁の数と一致するかどうかを調べて
;; 標準出力にCSV形式で出力する。
;; @param limit 調べる数値の上限
;; @example (main 10000)
(defun main (limit)
  (format t "Number,Number of multiples,Sum of each digits,Equal?,Factorization result~%")
  (do ((n 2 (incf n)))
      ((> n limit))
    (let (primes primes-compact sum-number-digits num-multiples)
      (setf primes (prime-factorization n)
	    primes-compact (compaction primes)
	    sum-number-digits (sum-digits n)
	    num-multiples (- (length primes-compact) 1))
      (format t "~A,~A,~A,~A,~S~%" n num-multiples sum-number-digits
	      (if (= num-multiples sum-number-digits) "Equal" "Not equal") primes-compact))))

(main 10000)