(34S) Prime Factors

[Thomas Klemm]

(05-30-2014 08:07 PM)Dave Britten Wrote:  My hunch is that repeatedly calling NEXTP like that causes a ton of duplicated work. I don't imagine there's any sophisticated caching going on with the limited RAM in the 30b hardware. (See: Schlemiel the Painter)

If that's the case, using it in a prime factoring algorithm is probably taking it to O(N * log N) complexity at best as the input argument grows, whereas the MOD 30 loop keeps it O(N) (even if it's not as fully optimal as it could be).

The important thing is: we don't need to know whether a factor is prime or not to figure out if it divides the number. What ever the complexity of PRIME? may be (O(k log³n) according to Wikipedia), it can't be faster than a simple division. Thus if NEXTP has to test all the next odd numbers we don't gain anything.
Using the MOD 30 loop you even gain a factor 1.875 compared to the minimal routine using only odd numbers.
How does your program compare to the built-in program PF?

Kind regards
Thomas