# Re: P35 Prime Factors

```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
```