Task

Write a program which counts up from   1,   displaying each number as the multiplication of its prime factors.

For the purpose of this task,   1   (unity)   may be shown as itself.



Example

      2   is prime,   so it would be shown as itself.

      6   is not prime;   it would be shown as   



2
×
3


{\displaystyle 2\times 3}

.
2144   is not prime;   it would be shown as   



2
×
2
×
2
×
2
×
2
×
67


{\displaystyle 2\times 2\times 2\times 2\times 2\times 67}

.



Related tasks

   prime decomposition
   factors of an integer
   Sieve of Eratosthenes
   primality by trial division
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes


(defparameter *primes*
  (make-array 10 :adjustable t :fill-pointer 0 :element-type 'integer))
 
(mapc #'(lambda (x) (vector-push x *primes*)) '(2 3 5 7))
 
(defun extend-primes (n)
  (let ((p (+ 2 (elt *primes* (1- (length *primes*))))))
    (loop for i = p then (+ 2 i)
	  while (<= (* i i) n) do
	  (if (primep i t) (vector-push-extend i *primes*)))))
 
(defun primep (n &optional skip)
  (if (not skip) (extend-primes n))
  (if (= n 1) nil
      (loop for p across *primes* while (<= (* p p) n)
	    never (zerop (mod n p)))))
 
(defun factors (n)
  (extend-primes n)
  (loop with res for x across *primes* while (> n (* x x)) do
	(loop while (zerop (rem n x)) do
	      (setf n (/ n x))
	      (push x res))
	finally (return (if (> n 1) (cons n res) res))))
 
(loop for n from 1 do
      (format t "~a: ~{~a~^ × ~}~%" n (reverse (factors n))))