Mercurial > hg > octave-nkf
annotate scripts/specfun/factor.m @ 9665:1dba57e9d08d
use blas_trans_type for xgemm
| author | Jaroslav Hajek <highegg@gmail.com> |
|---|---|
| date | Sat, 26 Sep 2009 10:41:07 +0200 |
| parents | 1231b1762a9a |
| children | f261f936bf36 |
| rev | line source |
|---|---|
| 8920 | 1 ## Copyright (C) 2000, 2006, 2007, 2009 Paul Kienzle |
| 5827 | 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 | |
| 7016 | 7 ## the Free Software Foundation; either version 3 of the License, or (at |
| 8 ## your option) any later version. | |
| 5827 | 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 | |
| 7016 | 16 ## along with Octave; see the file COPYING. If not, see |
| 17 ## <http://www.gnu.org/licenses/>. | |
| 5827 | 18 |
| 19 ## -*- texinfo -*- | |
|
9141
c1fff751b5a8
Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9051
diff
changeset
|
20 ## @deftypefn {Function File} {@var{p} =} factor (@var{q}) |
| 5827 | 21 ## @deftypefnx {Function File} {[@var{p}, @var{n}] =} factor (@var{q}) |
| 22 ## | |
|
9167
1231b1762a9a
Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9141
diff
changeset
|
23 ## Return prime factorization of @var{q}. That is, @code{prod (@var{p}) |
|
1231b1762a9a
Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9141
diff
changeset
|
24 ## == @var{q}} and every element of @var{p} is a prime number. If |
|
1231b1762a9a
Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9141
diff
changeset
|
25 ## @code{@var{q} == 1}, returns 1. |
| 5827 | 26 ## |
|
9167
1231b1762a9a
Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9141
diff
changeset
|
27 ## With two output arguments, return the unique primes @var{p} and |
|
1231b1762a9a
Simplify TeXinfo and eliminate use of @iftex in arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9141
diff
changeset
|
28 ## their multiplicities. That is, @code{prod (@var{p} .^ @var{n}) == |
| 6248 | 29 ## @var{q}}. |
|
9141
c1fff751b5a8
Update section 17.1 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents:
9051
diff
changeset
|
30 ## @seealso{gcd, lcm} |
| 5827 | 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, m] = factor (n) | |
| 41 | |
| 42 if (nargin < 1) | |
| 43 print_usage (); | |
| 44 endif | |
| 45 | |
| 46 if (! isscalar (n) || n != fix (n)) | |
| 47 error ("factor: n must be a scalar integer"); | |
| 48 endif | |
| 49 | |
| 8506 | 50 ## Special case of no primes less than sqrt(n). |
| 5827 | 51 if (n < 4) |
| 52 x = n; | |
| 53 m = 1; | |
| 54 return; | |
| 55 endif | |
| 56 | |
| 57 x = []; | |
| 58 ## There is at most one prime greater than sqrt(n), and if it exists, | |
| 59 ## it has multiplicity 1, so no need to consider any factors greater | |
| 60 ## than sqrt(n) directly. [If there were two factors p1, p2 > sqrt(n), | |
| 61 ## then n >= p1*p2 > sqrt(n)*sqrt(n) == n. Contradiction.] | |
| 62 p = primes (sqrt (n)); | |
| 63 while (n > 1) | |
| 8506 | 64 ## Find prime factors in remaining n. |
| 5827 | 65 q = n ./ p; |
| 66 p = p (q == fix (q)); | |
| 67 if (isempty (p)) | |
| 8506 | 68 ## Can't be reduced further, so n must itself be a prime. |
| 69 p = n; | |
| 5827 | 70 endif |
| 71 x = [x, p]; | |
| 8506 | 72 ## Reduce n. |
| 5827 | 73 n = n / prod (p); |
| 74 endwhile | |
| 75 x = sort (x); | |
| 76 | |
| 8506 | 77 ## Determine muliplicity. |
| 5827 | 78 if (nargout > 1) |
| 79 idx = find ([0, x] != [x, 0]); | |
| 80 x = x(idx(1:length(idx)-1)); | |
| 81 m = diff (idx); | |
| 82 endif | |
| 83 | |
| 84 endfunction | |
| 85 | |
| 86 ## test: | |
| 87 ## assert(factor(1),1); | |
| 88 ## for i=2:20 | |
| 89 ## p = factor(i); | |
| 90 ## assert(prod(p),i); | |
| 91 ## assert(all(isprime(p))); | |
| 92 ## [p,n] = factor(i); | |
| 93 ## assert(prod(p.^n),i); | |
| 94 ## assert(all([0,p]!=[p,0])); | |
| 95 ## end |