nvec ← ##.factors numb ⍝ Prime factors of ⍵ [factors] takes an integer scalar argument and returns a vector of ascending prime numbers whose product is ⍵. The stages in the process are: 1. Sequence: (2 .. ⍵*÷2),⍵ must contain all but at most one factor. 2. Extract those that divide ⍵ exactly. 3. Sieve out any multiples leaving only primes. 4. For each prime factor, replicate those powers that divide ⍵. 5. Append single factor greater than ⍵*÷2, if there is one. One weakness of this approach is that the vector generated in step 1 uses a lot of workspace, and will cause a WS FULL if ⍵ is more than about (⎕wa*2)÷2*8. For example, to extract the factors of a 10-digit phone number, we need around a megabyte and a half of available workspace. VMJ suggests that the initial sequence: (2 3 4 5 6 7 .. ⍵*÷2) be replaced by the sparser: (2,3 5 7 .. ⍵*÷2). This reduces both execution time and memory usage by a factor of around 2. In other words, the naïve coding: }(1↓⍳⌊⍵*÷2),⍵ ⍝ 2 .. sqrt(⍵),⍵ is replaced with: }2,(1+2×⍳⌊0.5×⍵*÷2) ⍝ 2,3 5 .. sqrt(⍵),⍵ The code could have been written as a series of assignments to local variables: seq0←2,(1+2×⍳⌊0.5×⍵*÷2) ⍝ 2,3 5 .. sqrt(⍵),⍵ seq1←(0=seq0|⍵)/seq0 ⍝ divisors of ⍵ in: ··· However, the large amount of workspace used for the first result would then have endured for the rest of the process. The approach taken here of using a "pipe- line" of functions: }{ ··· }{ ··· }{ ... ensures that intermediate results are released as soon as possible. Examples: factors +441256830030 ⍝ Dyalog phone number factors. 2 3 3 5 71 73 945949 factors +441256830031 ⍝ Dyalog fax number factors. 587 9007 83459 factors 4294967297 ⍝ 5th Fermat number, factored by Euler 1732. 641 6700417 {⍵≡factors×/⍵}sieve 2 to 30 ⍝ Factors of product of primes. 1 2 3 5{⍺≡∪factors×/⍺*⍵}4 5 6 ⍝ Unique factors of product of prime powers. 1 factors ⎕rl ⍝ Initial ⎕rl is 7*5. 7 7 7 7 7 See also: pco gcd sieve rational cfract nats rats Back to: contents Back to: Workspaces