Hi Alex, Joh-Tob, Thank you. With the Knuth reference the code makes a lot more sense!
I had implemented a more basic version. For large ranges, the performance difference of the Alex's iterative version that utilizes the sequence is much better! It is a very nice use of circular lists. : (bench (for X 3000000 (prime-factors X))) 16.547 sec -> (2 2 2 2 2 2 3 5 5 5 5 5 5) : (bench (for X 3000000 (primeFactorz X))) 24.632 sec -> (5 5 5 5 5 5 3 2 2 2 2 2 2) : (bench (prime-factors 100000000000)) 0.000 sec -> (2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5 5 5 5 5 5) : (bench (primeFactorz 100000000000)) 0.000 sec -> (5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 2 2 2 2) : (de primeFactorz (N) (use Result (recur (N) (let (Root (inc (sqrt N)) X 2) (when (gt0 (% N X)) (setq X 3) (while (and (gt0 (% N X)) (< (inc 'X 2) Root) ) ) ) (setq X (if (<= X Root) X N) Result (cons X Result) ) (unless (= X N) (recurse (/ N X))) ) ) Result ) ) /Lindsay On Sat, Feb 25, 2017 at 1:25 AM, Joh-Tob Schäg <johtob...@gmail.com> wrote: > I verified that it works for all numbers lower than 10000000. > > > My code: > (let N 2 > (while (> 10000000 N ) > (ifn (= N (apply '* (prime-factors N))) > (print N)) > (inc 'N))) > > 2017-02-25 9:58 GMT+01:00 Alexander Burger <a...@software-lab.de>: > >> Hi Lindsay, Joh-Tob, >> >> On Sat, Feb 25, 2017 at 09:36:04AM +0100, Joh-Tob Schäg wrote: >> > The purpose of the list is to increase the speed of the algorithm by >> > skipping some numbers. This is possible because of the math of >> Differences >> >> Correct. >> >> > between consecutive primes but i am currently verifying the algorithm >> if it >> > works, since the list might be wrong. >> >> I took it from Donald E. Knuth's "Art of Computer Programming", Volume 2 >> (Seminumerical Algorithms). In "Factoring into Primes" on page 365 he >> writes: >> >> The sequence ... of trial divisors .. can be taken to be simply 2, 3, >> 5, 7, >> 11, 13, 17, 19, 23, 25, 29, 31, 35, .. where we alternately add 2 and >> 4 after >> the first three terms. >> ... >> A further savings of 20 percent ... removing the numbers 30m +/- 5 .. >> >> I believe the term (let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) generates >> that >> sequence. >> >> ♪♫ Alex >> >> >> > >> > 2017-02-25 7:44 GMT+01:00 Lindsay John Lawrence < >> > lawrence.lindsayj...@gmail.com>: >> > >> > > Does anyone know the algorithm that is being expressed here? >> > > >> > > I am trying to understand the code... http://picolisp.com/wiki/?99p35 >> > > >> > > de prime-factors (N) >> > > (make >> > > (let (D 2 L (1 2 2 . (4 2 4 2 4 6 2 6 .)) M (sqrt N)) >> > > (while (>= M D) >> > > (if (=0 (% N D)) >> > > (setq M (sqrt (setq N (/ N (link D))))) >> > > (inc 'D (pop 'L)) ) ) >> > > (link N) ) ) ) >> > > >> > > and having difficulties understanding the purpose of the circular >> list. >> > > >> > > /Lindsay >> > > >> > > >> > > >> -- >> UNSUBSCRIBE: mailto:picolisp@software-lab.de?subject=Unsubscribe >> > >