Mercurial > hg > octave-nkf

annotate scripts/specfun/isprime.m @ 10664:faff5367cc05

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
second isprime rewrite
author Jaroslav Hajek <highegg@gmail.com>
date Wed, 26 May 2010 13:26:16 +0200
parents c6833d31f34e
children 0d9640d755b1
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
1 ## Copyright (C) 2000, 2006, 2007, 2009 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 -*-
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
21 ## @deftypefn {Function File} {} isprime (@var{n})
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
22 ## Return true if @var{n} is a prime number, false otherwise.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
23 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
24 ## If max(n) is very large, then you should be using special purpose
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
25 ## factorization code.
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
26 ##
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
27 ## @seealso{primes, factor, gcd, lcm}
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
28 ## @end deftypefn
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
29
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
30 function t = isprime (n)
7125
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
31
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
32 if (nargin == 1)
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
33 if (any ((n != floor (n) | n < 0)(:)))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
34 error ("isprime: needs positive integers");
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
35 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
36 maxn = max (n(:));
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
37 ## generate prime table of suitable length.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
38 maxp = min (maxn, max (sqrt (maxn), 1e7)); # FIXME: threshold not optimized.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
39 pr = primes (maxp);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
40 ## quick search for table matches.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
41 t = lookup (pr, n, "b");
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
42 ## take the rest.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
43 m = n(n > maxp);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
44 if (! isempty (m))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
45 ## there are still possible primes. filter them out by division.
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
46 if (maxn <= intmax ("uint32"))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
47 m = uint32 (m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
48 elseif (maxn <= intmax ("uint64"))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
49 m = uint64 (m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
50 else
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
51 warning ("isprime: too large integers being tested");
10657
c6833d31f34e optimize primes and isprime
Jaroslav Hajek <highegg@gmail.com>
parents: 9984
diff changeset
52 endif
10664
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
53 pr = cast (pr(pr <= sqrt (maxn)), class (m));
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
54 for p = pr
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
55 m = m(rem (m, p) != 0);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
56 if (length (m) < length (pr) / 10)
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
57 break;
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
58 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
59 endfor
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
60 pr = pr(pr > p);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
61 mm = arrayfun (@(x) all (rem (x, pr)), m);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
62 m = m(mm);
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
63 if (! isempty (m))
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
64 m = cast (sort (m), class (n));
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
65 t |= lookup (m, n, "b");
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
66 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
67 endif
faff5367cc05 second isprime rewrite
Jaroslav Hajek <highegg@gmail.com>
parents: 10657
diff changeset
68
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
69 else
7125
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
70 print_usage ();
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
71 endif
f084ba47812b [project @ 2007-11-08 02:29:23 by jwe]
jwe
parents: 7017
diff changeset
72
5827
1fe78adb91bc [project @ 2006-05-22 06:25:14 by jwe]
jwe
parents:
diff changeset
73 endfunction
9984
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
74
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
75 %!assert (isprime (4), logical (0));
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
76 %!assert (isprime (3), logical (1));
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
77 %!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
78 %!error isprime ()
d1cc2e0ddf55 isprime: produce logical result
John W. Eaton <jwe@octave.org>
parents: 7125
diff changeset
79 %!error isprime (1, 2)