"Fossies" - the Fresh Open Source Software Archive 
Member "mapm_4.9.5a/primenum.c" (21 Feb 2010, 6341 Bytes) of package /linux/misc/old/mapm-4.9.5a.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
For more information about "primenum.c" see the
Fossies "Dox" file reference documentation.
1
2 /*
3 * M_APM - primenum.c
4 *
5 * Copyright (C) 1999 - 2007 Michael C. Ring
6 *
7 * Permission to use, copy, and distribute this software and its
8 * documentation for any purpose with or without fee is hereby granted,
9 * provided that the above copyright notice appear in all copies and
10 * that both that copyright notice and this permission notice appear
11 * in supporting documentation.
12 *
13 * Permission to modify the software is granted. Permission to distribute
14 * the modified code is granted. Modifications are to be distributed by
15 * using the file 'license.txt' as a template to modify the file header.
16 * 'license.txt' is available in the official MAPM distribution.
17 *
18 * This software is provided "as is" without express or implied warranty.
19 */
20
21 /*
22 * $Id: primenum.c,v 1.10 2007/12/03 02:05:01 mike Exp $
23 *
24 * PRIME Number Generator using the MAPM Library
25 *
26 * $Log: primenum.c,v $
27 * Revision 1.10 2007/12/03 02:05:01 mike
28 * update version
29 *
30 * Revision 1.9 2007/12/03 02:00:42 mike
31 * Update license
32 *
33 * Revision 1.8 2003/05/31 22:42:25 mike
34 * update version for display
35 *
36 * Revision 1.7 2003/05/15 21:38:12 mike
37 * add MAPM version to output
38 *
39 * Revision 1.6 2002/11/03 23:00:21 mike
40 * Updated function parameters to use the modern style
41 *
42 * Revision 1.5 2002/02/12 20:52:16 mike
43 * add some needed comments and change the initial setups
44 *
45 * Revision 1.4 2001/02/18 16:02:33 mike
46 * filter out multiples of 2,3,5, and 7
47 *
48 * Revision 1.3 2001/02/15 23:11:13 mike
49 * slightly improved algorithm
50 *
51 * Revision 1.2 1999/07/12 02:36:23 mike
52 * added more usage and added more comments
53 *
54 * Revision 1.1 1999/07/12 02:31:23 mike
55 * Initial revision
56 */
57
58 #include <stdio.h>
59 #include <stdlib.h>
60 #include <string.h>
61 #include <math.h>
62 #include "m_apm.h"
63
64 extern int is_number_prime(M_APM);
65 extern void init_working_mapm(void);
66 extern void free_working_mapm(void);
67
68 #define FALSE 0
69 #define TRUE 1
70
71 char buffer[2048];
72
73 static M_APM M_limit, M_digit, M_quot, M_rem, M_tmp0, M_tmp1;
74
75
76 /****************************************************************************/
77
78 int main(int argc, char *argv[])
79 {
80 char version_info[80];
81 int ct;
82 /* declare the M_APM variables ... */
83 M_APM aa_mapm;
84 M_APM bb_mapm;
85 M_APM cc_mapm;
86 M_APM dd_mapm;
87
88 if (argc < 2)
89 {
90 m_apm_lib_short_version(version_info);
91
92 fprintf(stdout,
93 "Usage: primenum number\t\t\t[Version 1.4, MAPM Version %s]\n",
94 version_info);
95 fprintf(stdout,
96 " find the first 10 prime numbers starting with \'number\'\n");
97
98 exit(4);
99 }
100 /* now initialize the M_APM variables ... */
101 aa_mapm = m_apm_init();
102 bb_mapm = m_apm_init();
103 cc_mapm = m_apm_init();
104 dd_mapm = m_apm_init();
105
106 init_working_mapm();
107
108 m_apm_set_string(dd_mapm, argv[1]);
109
110 /*
111 * if input < 3, set start point = 3
112 */
113
114 if (m_apm_compare(dd_mapm, MM_Three) == -1)
115 {
116 m_apm_copy(dd_mapm, MM_Three);
117 }
118
119 /*
120 * make sure we start with an odd integer
121 */
122
123 m_apm_integer_divide(aa_mapm, dd_mapm, MM_Two);
124 m_apm_multiply(bb_mapm, MM_Two, aa_mapm);
125 m_apm_add(aa_mapm, MM_One, bb_mapm);
126
127 ct = 0;
128
129 while (TRUE)
130 {
131 if (is_number_prime(aa_mapm))
132 {
133 m_apm_to_integer_string(buffer, aa_mapm);
134 fprintf(stdout,"%s\n",buffer);
135
136 if (++ct == 10)
137 break;
138 }
139
140 m_apm_add(cc_mapm, MM_Two, aa_mapm);
141 m_apm_copy(aa_mapm, cc_mapm);
142 }
143
144 free_working_mapm();
145
146 m_apm_free(aa_mapm);
147 m_apm_free(bb_mapm);
148 m_apm_free(cc_mapm);
149 m_apm_free(dd_mapm);
150
151 m_apm_free_all_mem();
152
153 exit(0);
154 }
155
156 /****************************************************************************/
157
158 /*
159 * functions returns TRUE if the M_APM input number is prime
160 * FALSE if it is not
161 */
162 int is_number_prime(M_APM input)
163 {
164 int ii, ret, index;
165 char sbuf[32];
166
167 /*
168 * for reference:
169 *
170 * table size of 2 to filter multiples of 2 and 3
171 * table size of 8 to filter multiples of 2, 3 and 5
172 * table size of 480 to filter multiples of 2,3,5,7, and 11
173 *
174 * this increment table will filter out all numbers
175 * that are multiples of 2,3,5 and 7.
176 */
177
178 static char incr_table[48] = {
179 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
180 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6,
181 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 };
182
183 /*
184 * since the real algorithm starts at 11 (to syncronize
185 * with the increment table), we will cheat for numbers < 10.
186 */
187
188 if (m_apm_compare(input, MM_Ten) <= 0)
189 {
190 m_apm_to_integer_string(sbuf, input);
191 ii = atoi(sbuf);
192
193 if (ii == 2 || ii == 3 || ii == 5 || ii == 7)
194 return(TRUE);
195 else
196 return(FALSE);
197 }
198
199 ret = FALSE;
200 index = 0;
201
202 /*
203 * see if the input number is a
204 * multiple of 3, 5, or 7.
205 */
206
207 m_apm_integer_div_rem(M_quot, M_rem, input, MM_Three);
208 if (m_apm_sign(M_rem) == 0) /* remainder == 0 */
209 return(ret);
210
211 m_apm_integer_div_rem(M_quot, M_rem, input, MM_Five);
212 if (m_apm_sign(M_rem) == 0)
213 return(ret);
214
215 m_apm_set_long(M_digit, 7L);
216 m_apm_integer_div_rem(M_quot, M_rem, input, M_digit);
217 if (m_apm_sign(M_rem) == 0)
218 return(ret);
219
220 ii = m_apm_exponent(input) + 16;
221
222 m_apm_sqrt(M_tmp1, ii, input);
223 m_apm_add(M_limit, MM_Two, M_tmp1);
224
225 m_apm_set_long(M_digit, 11L); /* now start at '11' to check */
226
227 while (TRUE)
228 {
229 if (m_apm_compare(M_digit, M_limit) >= 0)
230 {
231 ret = TRUE;
232 break;
233 }
234
235 m_apm_integer_div_rem(M_quot, M_rem, input, M_digit);
236
237 if (m_apm_sign(M_rem) == 0) /* remainder == 0 */
238 break;
239
240 m_apm_set_long(M_tmp1, (long)incr_table[index]);
241 m_apm_add(M_tmp0, M_digit, M_tmp1);
242 m_apm_copy(M_digit, M_tmp0);
243
244 if (++index == 48)
245 index = 0;
246 }
247
248 return(ret);
249 }
250
251 /****************************************************************************/
252
253 void init_working_mapm()
254 {
255 M_limit = m_apm_init();
256 M_digit = m_apm_init();
257 M_quot = m_apm_init();
258 M_rem = m_apm_init();
259 M_tmp0 = m_apm_init();
260 M_tmp1 = m_apm_init();
261 }
262
263 /****************************************************************************/
264
265 void free_working_mapm()
266 {
267 m_apm_free(M_limit);
268 m_apm_free(M_digit);
269 m_apm_free(M_quot);
270 m_apm_free(M_rem);
271 m_apm_free(M_tmp0);
272 m_apm_free(M_tmp1);
273 }
274
275 /****************************************************************************/