Re: Newb: help with factoring function
Posted: Sun Mar 01, 2009 5:13 pm
I think that you should first write a function that gives you the next prime number, and then use this function in your factorization function.
Discuss and learn Lisp programming of all dialects. NOTICE: Site locked. No new users or posts.
http://www.lispforum.com/
Code: Select all
(defun primep (number)
(when (> number 1)
(loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))
(defun next-prime (number)
(loop for n from (+ number 1) when (primep n) return n))
(defun factor (num)
(do* ((factors nil (cons factor factors))
(current-num num (/ num (apply #'* factors)))
(factor (do((x (next-prime 0) (next-prime x)))
((or (zerop (rem current-num x)) (= current-num 1)) x))))
((= num (apply #'* factors)) (reverse factors))))
which doesn't need to multiply all factors found so far?anomaly wrote:Code: Select all
(current-num num (/ num (apply #'* factors)))
Harleqin wrote:Can you find a replacement for this line:
which doesn't need to multiply all factors found so far?anomaly wrote:Code: Select all
(current-num num (/ num (apply #'* factors)))
Code: Select all
(current-num num (/ current-num (first factors)))
Code: Select all
(defun primep (number)
(when (> number 1)
(loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))
(defun next-prime (number)
(loop for n from (+ number 1) when (primep n) return n))
(defun factor (num)
(loop for factors = nil then (cons factor factors)
for current-num = (/ current-num (first factors))
for factor = (unless (= current-num 1)
(loop for x from (next-prime 0) then (next-prime x)
until (zerop (rem current-num x))
finally (return x)))
until (= num (apply #'* factors))
finally (return (reverse factors))))
Code: Select all
(defun factor (num)
(do* ((factors nil (cons factor factors))
(current-num num (/ num (apply #'* factors)))
(factor (do ((x 2 (+ x 1)))
((or (zerop (rem current-num x)) (= current-num 1)) x))))
((= num (apply #'* factors)) (reverse factors))
))
Code: Select all
(defun factor (num)
(do* ((factors nil (cons factor factors))
(current-num num (/ num (apply #'* factors)))
(factor (do ((x 2 (+ x 1)))
((or (zerop (rem current-num x)) (= current-num 1)) x))
(do ((x 2 (+ x 1)))
((or (zerop (rem current-num x)) (= current-num 1)) x))))
((= num (apply #'* factors)) (reverse factors))
))