Mercurial > octave-nkf

annotate scripts/specfun/isprime.m @ 14138:72c96de7a403 stable

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
maint: update copyright notices for 2012
author John W. Eaton <jwe@octave.org>
date Mon, 02 Jan 2012 14:25:41 -0500
parents fd0a3ac60b0e
children f3d52523cde1
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
14138
72c96de7a403 maint: update copyright notices for 2012
John W. Eaton <jwe@octave.org>
parents: 11523
diff changeset
1 ## Copyright (C) 2000-2012 Paul Kienzle
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
2 ## Copyright (C) 2010 VZLU Prague
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
3 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
4 ## This file is part of Octave.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
5 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
6 ## Octave is free software; you can redistribute it and/or modify it
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
7 ## under the terms of the GNU General Public License as published by
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 5827
diff changeset
8 ## the Free Software Foundation; either version 3 of the License, or (at
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 5827
diff changeset
9 ## your option) any later version.
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
10 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
11 ## Octave is distributed in the hope that it will be useful, but
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
12 ## WITHOUT ANY WARRANTY; without even the implied warranty of
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
13 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
14 ## General Public License for more details.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
15 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
16 ## You should have received a copy of the GNU General Public License
7016
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 5827
diff changeset
17 ## along with Octave; see the file COPYING. If not, see
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 5827
diff changeset
18 ## <http://www.gnu.org/licenses/>.
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
19
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
20 ## -*- texinfo -*-
11431
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
21 ## @deftypefn {Function File} {} isprime (@var{x})
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
22 ## Return a logical array which is true where the elements of @var{x} are
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
23 ## prime numbers and false where they are not.
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
24 ##
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
25 ## If the maximum value in @var{x} is very large, then you should be using
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
26 ## special purpose factorization code.
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
27 ##
11431
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
28 ## @example
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
29 ## @group
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
30 ## isprime (1:6)
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
31 ## @result{} [0, 1, 1, 0, 1, 0]
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
32 ## @end group
0d9640d755b1 Improve docstrings for all isXXX functions.
Rik <octave@nomad.inbox5.com>
parents: 10664
diff changeset
33 ## @end example
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
34 ## @seealso{primes, factor, gcd, lcm}
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
35 ## @end deftypefn
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
36
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
37 function t = isprime (x)
7125
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
38
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
39 if (nargin == 1)
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
40 if (any ((x != floor (x) | x < 0)(:)))
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
41 error ("isprime: needs positive integers");
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
42 endif
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
43 maxn = max (x(:));
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
44 ## generate prime table of suitable length.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
45 maxp = min (maxn, max (sqrt (maxn), 1e7)); # FIXME: threshold not optimized.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
46 pr = primes (maxp);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
47 ## quick search for table matches.
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
48 t = lookup (pr, x, "b");
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
49 ## take the rest.
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
50 m = x(x > maxp);
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
51 if (! isempty (m))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
52 ## there are still possible primes. filter them out by division.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
53 if (maxn <= intmax ("uint32"))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
54 m = uint32 (m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
55 elseif (maxn <= intmax ("uint64"))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
56 m = uint64 (m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
57 else
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
58 warning ("isprime: too large integers being tested");
10657
c6833d31f34e optimize primes and isprime
Jaroslav Hajek <highegg@gmail.com>
parents: 9984
diff changeset
59 endif
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
60 pr = cast (pr(pr <= sqrt (maxn)), class (m));
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
61 for p = pr
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
62 m = m(rem (m, p) != 0);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
63 if (length (m) < length (pr) / 10)
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
64 break;
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
65 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
66 endfor
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
67 pr = pr(pr > p);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
68 mm = arrayfun (@(x) all (rem (x, pr)), m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
69 m = m(mm);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
70 if (! isempty (m))
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
71 m = cast (sort (m), class (x));
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
72 t |= lookup (m, x, "b");
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
73 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
74 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
75
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
76 else
7125
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
77 print_usage ();
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
78 endif
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
79
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
80 endfunction
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
81
11469
c776f063fefe Overhaul m-script files to use common variable name between code and documentation.
Rik <octave@nomad.inbox5.com>
parents: 11431
diff changeset
82
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
83 %!assert (isprime (4), logical (0));
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
84 %!assert (isprime (3), logical (1));
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
85 %!assert (isprime (magic (3)), logical ([0, 0, 0; 1, 1, 1; 0, 0, 1]));
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
86 %!error isprime ()
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
87 %!error isprime (1, 2)