# Re: P35 Prime Factors

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