Jason Sidabras

After an extensive amount of research on prime numbers I have finally figured out Problem 3 efficiently. I was going to go about creating a list of prime numbers, but the problem is every equation to generate prime numbers never generates all prime numbers. Just some number of them. Then they all have failures. On-the-other-hand, testing if a number is a prime number is a relatively easy procedure.

Two pieces of knowledge were needed to efficiently solve this problem: i) all numbers can be created by the multiplication of two or more prime numbers and ii) that at most a prime number can be is the square-root of the desired number. These two rules both limited the number of terms in the for loop (ii) and create a stopping rule (i).

So this is close to a sieve in that I am ignoring all non-primes. The stopping rule actually added 0.3 seconds to my problem, so i scratched it. On very large numbers it would save some time.

Problem 3

Find the largest prime factor of 317584931803.

(defun primep (x)
   ”Predicate to test the primality of x.”
   (let ((sqrt-x (sqrt x)))
   (do ((i 2 (+ 1 i)))
     ((> i sqrt-x) t)
     (when (eq (mod x i) 0)
   (return nil)))))

(defun problem3 (x)
   (let ((sqrt-x (sqrt x))
     (lst ‘(0)))
   (loop for i from 1 to sqrt-x
     do (cond ((eq (mod x i) 0)
       (cond ((primep i) (setq lst (append lst (multiple-value-list i))))))))
   (print lst)))

I learned a lot from this code. I learned how to use the let function to create private variables and learned how to use the append function. The other cool thing would have been a multiple-value-call function which is one of the crazy things only LISP can do because it treats everything like a string until execution. It would have allowed me to take a list and multiply the contents by calling out their values.

The slowest part of the code is the primep function. I will have to work on that to shave some more time off.

0.568 seconds of real time
0.472916 seconds of user run time
0.03995 seconds of system run time

Problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed one million.

This problem has nothing too special, except that it uses lisp’s awesome recursion techniques.

(defparameter *temp* 0)
(defun fib (n)
   ”Compute the N’th Fibonacci Number.”
   (if (or (zerop n) (= n 1))
      1
   (+ (fib (- n 1)) (fib (- N 2)))))

(defun problem2 ()
   (loop for x from 1 to 29
      do (if (evenp (fib x)) (setf *temp* (+ *temp* (fib x)))))
   (print *temp* ))

0.498 seconds of real time
0.456629 seconds of user run time
0.003151 seconds of system run time

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.