Mercurial > hg > octave-nkf

annotate scripts/miscellaneous/list_primes.m @ 17341:f4772605aec3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
debug.m: Fix spacing in @seealso macro (bug #39871) * scripts/miscellaneous/debug.m: Remove extra spaces within @seealso macro.
author Rik <rik@octave.org>
date Wed, 28 Aug 2013 11:07:03 -0700
parents 5bc9b9cb4362
children d63878346099
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: 12859
diff changeset
1 ## Copyright (C) 1993-2012 John W. Eaton
2313
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
2 ##
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
3 ## This file is part of Octave.
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
4 ##
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
5 ## Octave is free software; you can redistribute it and/or modify it
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
6 ## 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: 6248
diff changeset
7 ## the Free Software Foundation; either version 3 of the License, or (at
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6248
diff changeset
8 ## your option) any later version.
2313
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
9 ##
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
10 ## Octave is distributed in the hope that it will be useful, but
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
11 ## WITHOUT ANY WARRANTY; without even the implied warranty of
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
13 ## General Public License for more details.
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
14 ##
5ca126254d15 [project @ 1996-07-11 21:25:22 by jwe]
jwe
parents: 2311
diff changeset
15 ## 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: 6248
diff changeset
16 ## along with Octave; see the file COPYING. If not, see
93c65f2a5668 [project @ 2007-10-12 06:40:56 by jwe]
jwe
parents: 6248
diff changeset
17 ## <http://www.gnu.org/licenses/>.
245
16a24e76d6e0 [project @ 1993-12-03 02:00:15 by jwe]
jwe
parents: 68
diff changeset
18
3449
858695b3ed62 [project @ 2000-01-18 04:08:59 by jwe]
jwe
parents: 2847
diff changeset
19 ## -*- texinfo -*-
10687
a8ce6bdecce5 Improve documentation strings.
Rik <octave@nomad.inbox5.com>
parents: 9165
diff changeset
20 ## @deftypefn {Function File} {} list_primes ()
a8ce6bdecce5 Improve documentation strings.
Rik <octave@nomad.inbox5.com>
parents: 9165
diff changeset
21 ## @deftypefnx {Function File} {} list_primes (@var{n})
3449
858695b3ed62 [project @ 2000-01-18 04:08:59 by jwe]
jwe
parents: 2847
diff changeset
22 ## List the first @var{n} primes. If @var{n} is unspecified, the first
9165
8c71a86c4bf4 Update section 17.5 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 8920
diff changeset
23 ## 25 primes are listed.
2311
2b5788792cad [project @ 1996-07-11 20:18:38 by jwe]
jwe
parents: 2303
diff changeset
24 ##
9165
8c71a86c4bf4 Update section 17.5 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 8920
diff changeset
25 ## The algorithm used is from page 218 of the @TeX{}book.
8c71a86c4bf4 Update section 17.5 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 8920
diff changeset
26 ## @seealso{primes, isprime}
3449
858695b3ed62 [project @ 2000-01-18 04:08:59 by jwe]
jwe
parents: 2847
diff changeset
27 ## @end deftypefn
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
28
2314
949ab8eba8bc [project @ 1996-07-12 03:58:02 by jwe]
jwe
parents: 2313
diff changeset
29 ## Author: jwe
949ab8eba8bc [project @ 1996-07-12 03:58:02 by jwe]
jwe
parents: 2313
diff changeset
30
2311
2b5788792cad [project @ 1996-07-11 20:18:38 by jwe]
jwe
parents: 2303
diff changeset
31 function retval = list_primes (n)
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
32
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
33 if (nargin > 0)
4030
22bd65326ec1 [project @ 2002-08-09 18:58:13 by jwe]
jwe
parents: 3449
diff changeset
34 if (! isscalar (n))
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
35 error ("list_primes: argument must be a scalar");
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
36 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
37 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
38
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
39 if (nargin == 0)
9165
8c71a86c4bf4 Update section 17.5 (Utility Functions) of arith.txi
Rik <rdrider0-list@yahoo.com>
parents: 8920
diff changeset
40 n = 25;
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
41 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
42
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
43 if (n == 1)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
44 retval = 2;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
45 return;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
46 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
47
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
48 if (n == 2)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
49 retval = [2; 3];
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
50 return;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
51 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
52
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
53 retval = zeros (1, n);
14844
5bc9b9cb4362 maint: Use Octave coding conventions for cuddled parenthesis in retval assignments.
Rik <octave@nomad.inbox5.com>
parents: 14363
diff changeset
54 retval(1) = 2;
5bc9b9cb4362 maint: Use Octave coding conventions for cuddled parenthesis in retval assignments.
Rik <octave@nomad.inbox5.com>
parents: 14363
diff changeset
55 retval(2) = 3;
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
56
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
57 n = n - 2;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
58 i = 3;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
59 p = 5;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
60 while (n > 0)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
61
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
62 is_prime = 1;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
63 is_unknown = 1;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
64 d = 3;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
65 while (is_unknown)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
66 a = fix (p / d);
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
67 if (a <= d)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
68 is_unknown = 0;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
69 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
70 if (a * d == p)
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
71 is_prime = 0;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
72 is_unknown = 0;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
73 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
74 d = d + 2;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
75 endwhile
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
76
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
77 if (is_prime)
14844
5bc9b9cb4362 maint: Use Octave coding conventions for cuddled parenthesis in retval assignments.
Rik <octave@nomad.inbox5.com>
parents: 14363
diff changeset
78 retval(i++) = p;
68
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
79 n--;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
80 endif
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
81 p = p + 2;
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
82
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
83 endwhile
46807fe3db5b [project @ 1993-08-19 02:50:52 by jwe]
jwe
parents:
diff changeset
84
2326
7ffb2a630708 [project @ 1996-07-15 22:31:34 by jwe]
jwe
parents: 2314
diff changeset
85 endfunction
12859
372eb47cd6a5 Wrote 1 test for list_primes.m
Giles Anderson <agander@gmail.com>
parents: 11523
diff changeset
86
372eb47cd6a5 Wrote 1 test for list_primes.m
Giles Anderson <agander@gmail.com>
parents: 11523
diff changeset
87
14363
f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
88 %!assert (list_primes (), [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, ...
f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
89 %! 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])
f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
90 %!assert (list_primes (5), [2, 3, 5, 7, 11]);
f3d52523cde1 Use Octave coding conventions in all m-file %!test blocks
Rik <octave@nomad.inbox5.com>
parents: 14138
diff changeset
91