octave_packages/m/specfun/factor.m

   1 ## Copyright (C) 2000-2012 Paul Kienzle
   2 ##
   3 ## This file is part of Octave.
   4 ##
   5 ## Octave is free software; you can redistribute it and/or modify it
   6 ## under the terms of the GNU General Public License as published by
   7 ## the Free Software Foundation; either version 3 of the License, or (at
   8 ## your option) any later version.
   9 ##
  10 ## Octave is distributed in the hope that it will be useful, but
  11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
  12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13 ## General Public License for more details.
  14 ##
  15 ## You should have received a copy of the GNU General Public License
  16 ## along with Octave; see the file COPYING.  If not, see
  17 ## <http://www.gnu.org/licenses/>.
  18
  19 ## -*- texinfo -*-
  20 ## @deftypefn  {Function File} {@var{p} =} factor (@var{q})
  21 ## @deftypefnx {Function File} {[@var{p}, @var{n}] =} factor (@var{q})
  22 ##
  23 ## Return prime factorization of @var{q}.  That is,
  24 ## @code{prod (@var{p}) == @var{q}} and every element of @var{p} is a prime
  25 ## number.  If @code{@var{q} == 1}, return 1.
  26 ##
  27 ## With two output arguments, return the unique primes @var{p} and
  28 ## their multiplicities.  That is, @code{prod (@var{p} .^ @var{n}) ==
  29 ## @var{q}}.
  30 ## @seealso{gcd, lcm}
  31 ## @end deftypefn
  32
  33 ## Author: Paul Kienzle
  34
  35 ## 2002-01-28 Paul Kienzle
  36 ## * remove recursion; only check existing primes for multiplicity > 1
  37 ## * return multiplicity as suggested by Dirk Laurie
  38 ## * add error handling
  39
  40 function [x, n] = factor (q)
  41
  42   if (nargin < 1)
  43     print_usage ();
  44   endif
  45
  46   if (! isscalar (q) || q != fix (q))
  47     error ("factor: Q must be a scalar integer");
  48   endif
  49
  50   ## Special case of no primes less than sqrt(q).
  51   if (q < 4)
  52     x = q;
  53     n = 1;
  54     return;
  55   endif
  56
  57   x = [];
  58   ## There is at most one prime greater than sqrt(q), and if it exists,
  59   ## it has multiplicity 1, so no need to consider any factors greater
  60   ## than sqrt(q) directly. [If there were two factors p1, p2 > sqrt(q),
  61   ## then q >= p1*p2 > sqrt(q)*sqrt(q) == q. Contradiction.]
  62   p = primes (sqrt (q));
  63   while (q > 1)
  64     ## Find prime factors in remaining q.
  65     p = p (rem (q, p) == 0);
  66     if (isempty (p))
  67       ## Can't be reduced further, so q must itself be a prime.
  68       p = q;
  69     endif
  70     x = [x, p];
  71     ## Reduce q.
  72     q = q / prod (p);
  73   endwhile
  74   x = sort (x);
  75
  76   ## Determine muliplicity.
  77   if (nargout > 1)
  78     idx = find ([0, x] != [x, 0]);
  79     x = x(idx(1:length(idx)-1));
  80     n = diff (idx);
  81   endif
  82
  83 endfunction
  84
  85 %!test
  86 %!  assert(factor(1),1);
  87 %!  for i=2:20
  88 %!     p = factor(i);
  89 %!     assert(prod(p),i);
  90 %!     assert(all(isprime(p)));
  91 %!     [p,n] = factor(i);
  92 %!     assert(prod(p.^n),i);
  93 %!     assert(all([0,p]!=[p,0]));
  94 %!  endfor
  95