2 * prime - quickly determine if a small number is prime
4 * Copyright (C) 1999-2007 Landon Curt Noll
6 * Calc is open software; you can redistribute it and/or modify it under
7 * the terms of the version 2.1 of the GNU Lesser General Public License
8 * as published by the Free Software Foundation.
10 * Calc is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
13 * Public License for more details.
15 * A copy of version 2.1 of the GNU Lesser General Public License is
16 * distributed with calc under the filename COPYING-LGPL. You should have
17 * received a copy with calc; if not, write to Free Software Foundation, Inc.
18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 * @(#) $Revision: 30.1 $
21 * @(#) $Id: prime.c,v 30.1 2007/03/16 11:09:46 chongo Exp $
22 * @(#) $Source: /usr/local/src/bin/calc/RCS/prime.c,v $
24 * Under source code control: 1994/06/04 03:26:14
25 * File existed as early as: 1994
27 * chongo <was here> /\oo/\ http://www.isthe.com/chongo/
28 * Share and enjoy! :-) http://www.isthe.com/chongo/tech/comp/calc/
35 #include "have_const.h"
39 * odd prime bitmap for odd values < 2^16
41 * pr_map[i] & (1<<j) == 1 ==> i*16 + j*2 + 1 is prime
42 * 0 ==> i*16 + j*2 + 1 is not prime
44 * This table is useful to quickly determine if a 16 bit odd number
45 * is prime. Use the prime[] array to quickly walk thru the 16 bit
48 CONST
unsigned char pr_map
[(MAX_MAP_VAL
/8)+1] = {
49 110,203,180,100,154, 18,109,129, 50, 76, 74,134, 13,130,150, 33,
50 201, 52, 4, 90, 32, 97,137,164, 68, 17,134, 41,209,130, 40, 74,
51 48, 64, 66, 50, 33,153, 52, 8, 75, 6, 37, 66,132, 72,138, 20,
52 5, 66, 48,108, 8,180, 64, 11,160, 8, 81, 18, 40,137, 4,101,
53 152, 48, 76,128,150, 68, 18,128, 33, 66, 18, 65,201, 4, 33,192,
54 50, 45,152, 0, 0, 73, 4, 8,129,150,104,130,176, 37, 8, 34,
55 72,137,162, 64, 89, 38, 4,144, 6, 64, 67, 48, 68,146, 0,105,
56 16,130, 8, 8,164, 13, 65, 18, 96,192, 0, 36,210, 34, 97, 8,
57 132, 4, 27,130, 1,211, 16, 1, 2,160, 68,192, 34, 96,145, 20,
58 12, 64,166, 4,210,148, 32, 9,148, 32, 82, 0, 8, 16,162, 76,
59 0,130, 1, 81, 16, 8,139,164, 37,154, 48, 68,129, 16, 76, 3,
60 2, 37, 82,128, 8, 73,132, 32, 80, 50, 0, 24,162, 64, 17, 36,
61 40, 1,132, 1, 1,160, 65, 10, 18, 69, 0, 54, 8, 0, 38, 41,
62 131,130, 97,192,128, 4, 16, 16,109, 0, 34, 72, 88, 38, 12,194,
63 16, 72,137, 36, 32, 88, 32, 69,136, 36, 0, 25, 2, 37,192, 16,
64 104, 8, 20, 1,202, 50, 40,128, 0, 4, 75, 38, 0, 19,144, 96,
65 130,128, 37,208, 0, 1, 16, 50, 12, 67,134, 33, 17, 0, 8, 67,
66 36, 4, 72, 16, 12,144,146, 0, 67, 32, 45, 0, 6, 9,136, 36,
67 64,192, 50, 9, 9,130, 0, 83,128, 8,128,150, 65,129, 0, 64,
68 72, 16, 72, 8,150, 72, 88, 32, 41,195,128, 32, 2,148, 96,146,
69 0, 32,129, 34, 68, 16,160, 5, 64,144, 1, 73, 32, 4, 10, 0,
70 36,137, 52, 72, 19,128, 44,192,130, 41, 0, 36, 69, 8, 0, 8,
71 152, 54, 4, 82,132, 4,208, 4, 0,138,144, 68,130, 50,101, 24,
72 144, 0, 10, 2, 1, 64, 2, 40, 64,164, 4,146, 48, 4, 17,134,
73 8, 66, 0, 44, 82, 4, 8,201,132, 96, 72, 18, 9,153, 36, 68,
74 0, 36, 0, 3, 20, 33, 0, 16, 1, 26, 50, 5,136, 32, 64, 64,
75 6, 9,195,132, 64, 1, 48, 96, 24, 2,104, 17,144, 12, 2,162,
76 4, 0,134, 41,137, 20, 36,130, 2, 65, 8,128, 4, 25,128, 8,
77 16, 18,104, 66,164, 4, 0, 2, 97, 16, 6, 12, 16, 0, 1, 18,
78 16, 32, 3,148, 33, 66, 18,101, 24,148, 12, 10, 4, 40, 1, 20,
79 41, 10,164, 64,208, 0, 64, 1,144, 4, 65, 32, 45, 64,130, 72,
80 193, 32, 0, 16, 48, 1, 8, 36, 4, 89,132, 36, 0, 2, 41,130,
81 0, 97, 88, 2, 72,129, 22, 72, 16, 0, 33, 17, 6, 0,202,160,
82 64, 2, 0, 4,145,176, 0, 66, 4, 12,129, 6, 9, 72, 20, 37,
83 146, 32, 37, 17,160, 0, 10,134, 12,193, 2, 72, 0, 32, 69, 8,
84 50, 0,152, 6, 4, 19, 34, 0,130, 4, 72,129, 20, 68,130, 18,
85 36, 24, 16, 64, 67,128, 40,208, 4, 32,129, 36,100,216, 0, 44,
86 9, 18, 8, 65,162, 0, 0, 2, 65,202, 32, 65,192, 16, 1, 24,
87 164, 4, 24,164, 32, 18,148, 32,131,160, 64, 2, 50, 68,128, 4,
88 0, 24, 0, 12, 64,134, 96,138, 0,100,136, 18, 5, 1,130, 0,
89 74,162, 1,193, 16, 97, 9, 4, 1,136, 0, 96, 1,180, 64, 8,
90 6, 1, 3,128, 8, 64,148, 4,138, 32, 41,128, 2, 12, 82, 2,
91 1, 66,132, 0,128,132,100, 2, 50, 72, 0, 48, 68, 64, 34, 33,
92 0, 2, 8,195,160, 4,208, 32, 64, 24, 22, 64, 64, 0, 40, 82,
93 144, 8,130, 20, 1, 24, 16, 8, 9,130, 64, 10,160, 32,147,128,
94 8,192, 0, 32, 82, 0, 5, 1, 16, 64, 17, 6, 12,130, 0, 0,
95 75,144, 68,154, 0, 40,128,144, 4, 74, 6, 9, 67, 2, 40, 0,
96 52, 1, 24, 0,101, 9,128, 68, 3, 0, 36, 2,130, 97, 72, 20,
97 65, 0, 18, 40, 0, 52, 8, 81, 4, 5, 18,144, 40,137,132, 96,
98 18, 16, 73, 16, 38, 64, 73,130, 0,145, 16, 1, 10, 36, 64,136,
99 16, 76, 16, 4, 0, 80,162, 44, 64,144, 72, 10,176, 1, 80, 18,
100 8, 0,164, 4, 9,160, 40,146, 2, 0, 67, 16, 33, 2, 32, 65,
101 129, 50, 0, 8, 4, 12, 82, 0, 33, 73,132, 32, 16, 2, 1,129,
102 16, 72, 64, 34, 1, 1,132,105,193, 48, 1,200, 2, 68,136, 0,
103 12, 1, 2, 45,192, 18, 97, 0,160, 0,192, 48, 64, 1, 18, 8,
104 11, 32, 0,128,148, 64, 1,132, 64, 0, 50, 0, 16,132, 0, 11,
105 36, 0, 1, 6, 41,138,132, 65,128, 16, 8, 8,148, 76, 3,128,
106 1, 64,150, 64, 65, 32, 32, 80, 34, 37,137,162, 64, 64,164, 32,
107 2,134, 40, 1, 32, 33, 74, 16, 8, 0, 20, 8, 64, 4, 37, 66,
108 2, 33, 67, 16, 4,146, 0, 33, 17,160, 76, 24, 34, 9, 3,132,
109 65,137, 16, 4,130, 34, 36, 1, 20, 8, 8,132, 8,193, 0, 9,
110 66,176, 65,138, 2, 0,128, 54, 4, 73,160, 36,145, 0, 0, 2,
111 148, 65,146, 2, 1, 8, 6, 8, 9, 0, 1,208, 22, 40,137,128,
112 96, 0, 0,104, 1,144, 12, 80, 32, 1, 64,128, 64, 66, 48, 65,
113 0, 32, 37,129, 6, 64, 73, 0, 8, 1, 18, 73, 0,160, 32, 24,
114 48, 5, 1,166, 0, 16, 36, 40, 0, 2, 32,200, 32, 0,136, 18,
115 12,144,146, 0, 2, 38, 1, 66, 22, 73, 0, 4, 36, 66, 2, 1,
116 136,128, 12, 26,128, 8, 16, 0, 96, 2,148, 68,136, 0,105, 17,
117 48, 8, 18,160, 36, 19,132, 0,130, 0,101,192, 16, 40, 0, 48,
118 4, 3, 32, 1, 17, 6, 1,200,128, 0,194, 32, 8, 16,130, 12,
119 19, 2, 12, 82, 6, 64, 0,176, 97, 64, 16, 1,152,134, 4, 16,
120 132, 8,146, 20, 96, 65,128, 65, 26, 16, 4,129, 34, 64, 65, 32,
121 41, 82, 0, 65, 8, 52, 96, 16, 0, 40, 1, 16, 64, 0,132, 8,
122 66,144, 32, 72, 4, 4, 82, 2, 0, 8, 32, 4, 0,130, 13, 0,
123 130, 64, 2, 16, 5, 72, 32, 64,153, 0, 0, 1, 6, 36,192, 0,
124 104,130, 4, 33, 18, 16, 68, 8, 4, 0, 64,166, 32,208, 22, 9,
125 201, 36, 65, 2, 32, 12, 9,146, 64, 18, 0, 0, 64, 0, 9, 67,
126 132, 32,152, 2, 1, 17, 36, 0, 67, 36, 0, 3,144, 8, 65, 48,
127 36, 88, 32, 76,128,130, 8, 16, 36, 37,129, 6, 65, 9, 16, 32,
128 24, 16, 68,128, 16, 0, 74, 36, 13, 1,148, 40,128, 48, 0,192,
129 2, 96, 16,132, 12, 2, 0, 9, 2,130, 1, 8, 16, 4,194, 32,
130 104, 9, 6, 4, 24, 0, 0, 17,144, 8, 11, 16, 33,130, 2, 12,
131 16,182, 8, 0, 38, 0, 65, 2, 1, 74, 36, 33, 26, 32, 36,128,
132 0, 68, 2, 0, 45, 64, 2, 0,139,148, 32, 16, 0, 32,144,166,
133 64, 19, 0, 44, 17,134, 97, 1,128, 65, 16, 2, 4,129, 48, 72,
134 72, 32, 40, 80,128, 33,138, 16, 4, 8, 16, 9, 16, 16, 72, 66,
135 160, 12,130,146, 96,192, 32, 5,210, 32, 64, 1, 0, 4, 8,130,
136 45,130, 2, 0, 72,128, 65, 72, 16, 0,145, 4, 4, 3,132, 0,
137 194, 4,104, 0, 0,100,192, 34, 64, 8, 50, 68, 9,134, 0,145,
138 2, 40, 1, 0,100, 72, 0, 36, 16,144, 0, 67, 0, 33, 82,134,
139 65,139,144, 32, 64, 32, 8,136, 4, 68, 19, 32, 0, 2,132, 96,
140 129,144, 36, 64, 48, 0, 8, 16, 8, 8, 2, 1, 16, 4, 32, 67,
141 180, 64,144, 18,104, 1,128, 76, 24, 0, 8,192, 18, 73, 64, 16,
142 36, 26, 0, 65,137, 36, 76, 16, 0, 4, 82, 16, 9, 74, 32, 65,
143 72, 34,105, 17, 20, 8, 16, 6, 36,128,132, 40, 0, 16, 0, 64,
144 16, 1, 8, 38, 8, 72, 6, 40, 0, 20, 1, 66,132, 4, 10, 32,
145 0, 1,130, 8, 0,130, 36, 18, 4, 64, 64,160, 64,144, 16, 4,
146 144, 34, 64, 16, 32, 44,128, 16, 40, 67, 0, 4, 88, 0, 1,129,
147 16, 72, 9, 32, 33,131, 4, 0, 66,164, 68, 0, 0,108, 16,160,
148 68, 72,128, 0,131,128, 72,201, 0, 0, 0, 2, 5, 16,176, 4,
149 19, 4, 41, 16,146, 64, 8, 4, 68,130, 34, 0, 25, 32, 0, 25,
150 32, 1,129,144, 96,138, 0, 65,192, 2, 69, 16, 4, 0, 2,162,
151 9, 64, 16, 33, 73, 32, 1, 66, 48, 44, 0, 20, 68, 1, 34, 4,
152 2,146, 8,137, 4, 33,128, 16, 5, 1, 32, 64, 65,128, 4, 0,
153 18, 9, 64,176,100, 88, 50, 1, 8,144, 0, 65, 4, 9,193,128,
154 97, 8,144, 0,154, 0, 36, 1, 18, 8, 2, 38, 5,130, 6, 8,
155 8, 0, 32, 72, 32, 0, 24, 36, 72, 3, 2, 0, 17, 0, 9, 0,
156 132, 1, 74, 16, 1,152, 0, 4, 24,134, 0,192, 0, 32,129,128,
157 4, 16, 48, 5, 0,180, 12, 74,130, 41,145, 2, 40, 0, 32, 68,
158 192, 0, 44,145,128, 64, 1,162, 0, 18, 4, 9,195, 32, 0, 8,
159 2, 12, 16, 34, 4, 0, 0, 44, 17,134, 0,192, 0, 0, 18, 50,
160 64,137,128, 64, 64, 2, 5, 80,134, 96,130,164, 96, 10, 18, 77,
161 128,144, 8, 18,128, 9, 2, 20, 72, 1, 36, 32,138, 0, 68,144,
162 4, 4, 1, 2, 0,209, 18, 0, 10, 4, 64, 0, 50, 33,129, 36,
163 8, 25,132, 32, 2, 4, 8,137,128, 36, 2, 2,104, 24,130, 68,
164 66, 0, 33, 64, 0, 40, 1,128, 69,130, 32, 64, 17,128, 12, 2,
165 0, 36, 64,144, 1, 64, 32, 32, 80, 32, 40, 25, 0, 64, 9, 32,
166 8,128, 4, 96, 64,128, 32, 8, 48, 73, 9, 52, 0, 17, 36, 36,
167 130, 0, 65,194, 0, 4,146, 2, 36,128, 0, 12, 2,160, 0, 1,
168 6, 96, 65, 4, 33,208, 0, 1, 1, 0, 72, 18,132, 4,145, 18,
169 8, 0, 36, 68, 0, 18, 65, 24, 38, 12, 65,128, 0, 82, 4, 32,
170 9, 0, 36,144, 32, 72, 24, 2, 0, 3,162, 9,208, 20, 0,138,
171 132, 37, 74, 0, 32,152, 20, 64, 0,162, 5, 0, 0, 0, 64, 20,
172 1, 88, 32, 44,128,132, 0, 9, 32, 32,145, 2, 8, 2,176, 65,
173 8, 48, 0, 9, 16, 0, 24, 2, 33, 2, 2, 0, 0, 36, 68, 8,
174 18, 96, 0,178, 68, 18, 2, 12,192,128, 64,200, 32, 4, 80, 32,
175 5, 0,176, 4, 11, 4, 41, 83, 0, 97, 72, 48, 0,130, 32, 41,
176 0, 22, 0, 83, 34, 32, 67, 16, 72, 0,128, 4,210, 0, 64, 0,
177 162, 68, 3,128, 41, 0, 4, 8,192, 4,100, 64, 48, 40, 9,132,
178 68, 80,128, 33, 2,146, 0,192, 16, 96,136, 34, 8,128, 0, 0,
179 24,132, 4,131,150, 0,129, 32, 5, 2, 0, 69,136,132, 0, 81,
180 32, 32, 81,134, 65, 75,148, 0,128, 0, 8, 17, 32, 76, 88,128,
181 4, 3, 6, 32,137, 0, 5, 8, 34, 5,144, 0, 64, 0,130, 9,
182 80, 0, 0, 0,160, 65,194, 32, 8, 0, 22, 8, 64, 38, 33,208,
183 144, 8,129,144, 65, 0, 2, 68, 8, 16, 12, 10,134, 9,144, 4,
184 0,200,160, 4, 8, 48, 32,137,132, 0, 17, 34, 44, 64, 0, 8,
185 2,176, 1, 72, 2, 1, 9, 32, 4, 3, 4, 0,128, 2, 96, 66,
186 48, 33, 74, 16, 68, 9, 2, 0, 1, 36, 0, 18,130, 33,128,164,
187 32, 16, 2, 4,145,160, 64, 24, 4, 0, 2, 6,105, 9, 0, 5,
188 88, 2, 1, 0, 0, 72, 0, 0, 0, 3,146, 32, 0, 52, 1,200,
189 32, 72, 8, 48, 8, 66,128, 32,145,144,104, 1, 4, 64, 18, 2,
190 97, 0, 18, 8, 1,160, 0, 17, 4, 33, 72, 4, 36,146, 0, 12,
191 1,132, 4, 0, 0, 1, 18,150, 64, 1,160, 65,136, 34, 40,136,
192 0, 68, 66,128, 36, 18, 20, 1, 66,144, 96, 26, 16, 4,129, 16,
193 72, 8, 6, 41,131, 2, 64, 2, 36,100,128, 16, 5,128, 16, 64,
194 2, 2, 8, 66,132, 1, 9, 32, 4, 80, 0, 96, 17, 48, 64, 19,
195 2, 4,129, 0, 9, 8, 32, 69, 74, 16, 97,144, 38, 12, 8, 2,
196 33,145, 0, 96, 2, 4, 0, 2, 0, 12, 8, 6, 8, 72,132, 8,
197 17, 2, 0,128,164, 0, 90, 32, 0,136, 4, 4, 2, 0, 9, 0,
198 20, 8, 73, 20, 32,200, 0, 4,145,160, 64, 89,128, 0, 18, 16,
199 0,128,128,101, 0, 0, 4, 0,128, 64, 25, 0, 33, 3,132, 96,
200 192, 4, 36, 26, 18, 97,128,128, 8, 2, 4, 9, 66, 18, 32, 8,
201 52, 4,144, 32, 1, 1,160, 0, 11, 0, 8,145,146, 64, 2, 52,
202 64,136, 16, 97, 25, 2, 0, 64, 4, 37,192,128,104, 8, 4, 33,
203 128, 34, 4, 0,160, 12, 1,132, 32, 65, 0, 8,138, 0, 32,138,
204 0, 72,136, 4, 4, 17,130, 8, 64,134, 9, 73,164, 64, 0, 16,
205 1, 1,162, 4, 80,128, 12,128, 0, 72,130,160, 1, 24, 18, 65,
206 1, 4, 72, 65, 0, 36, 1, 0, 0,136, 20, 0, 2, 0,104, 1,
207 32, 8, 74, 34, 8,131,128, 0,137, 4, 1,194, 0, 0, 0, 52,
208 4, 0,130, 40, 2, 2, 65, 74,144, 5,130, 2, 9,128, 36, 4,
209 65, 0, 1,146,128, 40, 1, 20, 0, 80, 32, 76, 16,176, 4, 67,
210 164, 33,144, 4, 1, 2, 0, 68, 72, 0,100, 8, 6, 0, 66, 32,
211 8, 2,146, 1, 74, 0, 32, 80, 50, 37,144, 34, 4, 9, 0, 8,
212 17,128, 33, 1, 16, 5, 0, 50, 8,136,148, 8, 8, 36, 13,193,
213 128, 64, 11, 32, 64, 24, 18, 4, 0, 34, 64, 16, 38, 5,193,130,
214 0, 1, 48, 36, 2, 34, 65, 8, 36, 72, 26, 0, 37,210, 18, 40,
215 66, 0, 4, 64, 48, 65, 0, 2, 0, 19, 32, 36,209,132, 8,137,
216 128, 4, 82, 0, 68, 24,164, 0, 0, 6, 32,145, 16, 9, 66, 32,
217 36, 64, 48, 40, 0,132, 64, 64,128, 8, 16, 4, 9, 8, 4, 64,
218 8, 34, 0, 25, 2, 0, 0,128, 44, 2, 2, 33, 1,144, 32, 64,
219 0, 12, 0, 52, 72, 88, 32, 1, 67, 4, 32,128, 20, 0,144, 0,
220 109, 17, 0, 0, 64, 32, 0, 3, 16, 64,136, 48, 5, 74, 0,101,
221 16, 36, 8, 24,132, 40, 3,128, 32, 66,176, 64, 0, 16,105, 25,
222 4, 0, 0,128, 4,194, 4, 0, 1, 0, 5, 0, 34, 37, 8,150,
223 4, 2, 34, 0,208, 16, 41, 1,160, 96, 8, 16, 4, 1, 22, 68,
224 16, 2, 40, 2,130, 72, 64,132, 32,144, 34, 40,128, 4, 0, 64,
225 4, 36, 0,128, 41, 3, 16, 96, 72, 0, 0,129,160, 0, 81, 32,
226 12,209, 0, 1, 65, 32, 4,146, 0, 0, 16,146, 0, 66, 4, 5,
227 1,134, 64,128, 16, 32, 82, 32, 33, 0, 16, 72, 10, 2, 0,208,
228 18, 65, 72,128, 4, 0, 0, 72, 9, 34, 4, 0, 36, 0, 67, 16,
229 96, 10, 0, 68, 18, 32, 44, 8, 32, 68, 0,132, 9, 64, 6, 8,
230 193, 0, 64,128, 32, 0,152, 18, 72, 16,162, 32, 0,132, 72,192,
231 16, 32,144, 18, 8,152,130, 0, 10,160, 4, 3, 0, 40,195, 0,
232 68, 66, 16, 4, 8, 4, 64, 0, 0, 5, 16, 0, 33, 3,128, 4,
233 136, 18,105, 16, 0, 4, 8, 4, 4, 2,132, 72, 73, 4, 32, 24,
234 2,100,128, 48, 8, 1, 2, 0, 82, 18, 73, 8, 32, 65,136, 16,
235 72, 8, 52, 0, 1,134, 5,208, 0, 0,131,132, 33, 64, 2, 65,
236 16,128, 72, 64,162, 32, 81, 0, 0, 73, 0, 1,144, 32, 64, 24,
237 2, 64, 2, 34, 5, 64,128, 8,130, 16, 32, 24, 0, 5, 1,130,
238 64, 88, 0, 4,129,144, 41, 1,160,100, 0, 34, 64, 1,162, 0,
239 24, 4, 13, 0, 0, 96,128,148, 96,130, 16, 13,128, 48, 12, 18,
240 32, 0, 0, 18, 64,192, 32, 33, 88, 2, 65, 16,128, 68, 3, 2,
241 4, 19,144, 41, 8, 0, 68,192, 0, 33, 0, 38, 0, 26,128, 1,
242 19, 20, 32, 10, 20, 32, 0, 50, 97, 8, 0, 64, 66, 32, 9,128,
243 6, 1,129,128, 96, 66, 0,104,144,130, 8, 66,128, 4, 2,128,
244 9, 11, 4, 0,152, 0, 12,129, 6, 68, 72,132, 40, 3,146, 0,
245 1,128, 64, 10, 0, 12,129, 2, 8, 81, 4, 40,144, 2, 32, 9,
246 16, 96, 0, 0, 9,129,160, 12, 0,164, 9, 0, 2, 40,128, 32,
247 0, 2, 2, 4,129, 20, 4, 0, 4, 9, 17, 18, 96, 64, 32, 1,
248 72, 48, 64, 17, 0, 8, 10,134, 0, 0, 4, 96,129, 4, 1,208,
249 2, 65, 24,144, 0, 10, 32, 0,193, 6, 1, 8,128,100,202, 16,
250 4,153,128, 72, 1,130, 32, 80,144, 72,128,132, 32,144, 34, 0,
251 25, 0, 4, 24, 32, 36, 16,134, 64,194, 0, 36, 18, 16, 68, 0,
252 22, 8, 16, 36, 0, 18, 6, 1, 8,144, 0, 18, 2, 77, 16,128,
253 64, 80, 34, 0, 67, 16, 1, 0, 48, 33, 10, 0, 0, 1, 20, 0,
254 16,132, 4,193, 16, 41, 10, 0, 1,138, 0, 32, 1, 18, 12, 73,
255 32, 4,129, 0, 72, 1, 4, 96,128, 18, 12, 8, 16, 72, 74, 4,
256 40, 16, 0, 40, 64,132, 69, 80, 16, 96, 16, 6, 68, 1,128, 9,
257 0,134, 1, 66,160, 0,144, 0, 5,144, 34, 64, 65, 0, 8,128,
258 2, 8,192, 0, 1, 88, 48, 73, 9, 20, 0, 65, 2, 12, 2,128,
259 64,137, 0, 36, 8, 16, 5,144, 50, 64, 10,130, 8, 0, 18, 97,
260 0, 4, 33, 0, 34, 4, 16, 36, 8, 10, 4, 1, 16, 0, 32, 64,
261 132, 4,136, 34, 32,144, 18, 0, 83, 6, 36, 1, 4, 64, 11, 20,
262 96,130, 2, 13, 16,144, 12, 8, 32, 9, 0, 20, 9,128,128, 36,
263 130, 0, 64, 1, 2, 68, 1, 32, 12, 64,132, 64, 10, 16, 65, 0,
264 48, 5, 9,128, 68, 8, 32, 32, 2, 0, 73, 67, 32, 33, 0, 32,
265 0, 1,182, 8, 64, 4, 8, 2,128, 1, 65,128, 64, 8, 16, 36,
266 0, 32, 4, 18,134, 9,192, 18, 33,129, 20, 4, 0, 2, 32,137,
267 180, 68, 18,128, 0,209, 0,105, 64,128, 0, 66, 18, 0, 24, 4,
268 0, 73, 6, 33, 2, 4, 40, 2,132, 1,192, 16,104, 0, 32, 8,
269 64, 0, 8,145, 16, 1,129, 36, 4,210, 16, 76,136,134, 0, 16,
270 128, 12, 2, 20, 0,138,144, 64, 24, 32, 33,128,164, 0, 88, 36,
271 32, 16, 16, 96,193, 48, 65, 72, 2, 72, 9, 0, 64, 9, 2, 5,
272 17,130, 32, 74, 32, 36, 24, 2, 12, 16, 34, 12, 10, 4, 0, 3,
273 6, 72, 72, 4, 4, 2, 0, 33,128,132, 0, 24, 0, 12, 2, 18,
274 1, 0, 20, 5,130, 16, 65,137, 18, 8, 64,164, 33, 1,132, 72,
275 2, 16, 96, 64, 2, 40, 0, 20, 8, 64,160, 32, 81, 18, 0,194,
276 0, 1, 26, 48, 64,137, 18, 76, 2,128, 0, 0, 20, 1, 1,160,
277 33, 24, 34, 33, 24, 6, 64, 1,128, 0,144, 4, 72, 2, 48, 4,
278 8, 0, 5,136, 36, 8, 72, 4, 36, 2, 6, 0,128, 0, 0, 0,
279 16,101, 17,144, 0, 10,130, 4,195, 4, 96, 72, 36, 4,146, 2,
280 68,136,128, 64, 24, 6, 41,128, 16, 1, 0, 0, 68,200, 16, 33,
281 137, 48, 0, 75,160, 1, 16, 20, 0, 2,148, 64, 0, 32,101, 0,
282 162, 12, 64, 34, 32,129, 18, 32,130, 4, 1, 16, 0, 8,136, 0,
283 0, 17,128, 4, 66,128, 64, 65, 20, 0, 64, 50, 44,128, 36, 4,
284 25, 0, 0,145, 0, 32,131, 0, 5, 64, 32, 9, 1,132, 64, 64,
285 32, 32, 17, 0, 64, 65,144, 32, 0, 0, 64,144,146, 72, 24, 6,
286 8,129,128, 72, 1, 52, 36, 16, 32, 4, 0, 32, 4, 24, 6, 45,
287 144, 16, 1, 0,144, 0, 10, 34, 1, 0, 34, 0, 17,132, 1, 1,
288 0, 32,136, 0, 68, 0, 34, 1, 0,166, 64, 2, 6, 32, 17, 0,
289 1,200,160, 4,138, 0, 40, 25,128, 0, 82,160, 36, 18, 18, 9,
290 8, 36, 1, 72, 0, 4, 0, 36, 64, 2,132, 8, 0, 4, 72, 64,
291 144, 96, 10, 34, 1,136, 20, 8, 1, 2, 8,211, 0, 32,192,144,
292 36, 16, 0, 0, 1,176, 8, 10,160, 0,128, 0, 1, 9, 0, 32,
293 82, 2, 37, 0, 36, 4, 2,132, 36, 16,146, 64, 2,160, 64, 0,
294 34, 8, 17, 4, 8, 1, 34, 0, 66, 20, 0, 9,144, 33, 0, 48,
295 108, 0, 0, 12, 0, 34, 9,144, 16, 40, 64, 0, 32,192, 32, 0,
296 144, 0, 64, 1,130, 5, 18, 18, 9,193, 4, 97,128, 2, 40,129,
297 36, 0, 73, 4, 8, 16,134, 41, 65,128, 33, 10, 48, 73,136,144,
298 0, 65, 4, 41,129,128, 65, 9, 0, 64, 18, 16, 64, 0, 16, 64,
299 72, 2, 5,128, 2, 33, 64, 32, 0, 88, 32, 96, 0,144, 72, 0,
300 128, 40,192,128, 72, 0, 0, 68,128, 2, 0, 9, 6, 0, 18, 2,
301 1, 0, 16, 8,131, 16, 69, 18, 0, 44, 8, 4, 68, 0, 32, 32,
302 192, 16, 32, 1, 0, 5,200, 32, 4,152, 16, 8, 16, 0, 36, 2,
303 22, 64,136, 0, 97,136, 18, 36,128,166, 0, 66, 0, 8, 16, 6,
304 72, 64,160, 0, 80, 32, 4,129,164, 64, 24, 0, 8, 16,128, 1
310 * This table is useful to walk thru 16 bit odd primes to factor a 32 bit
311 * value. Use the pr_map[] array to quickly determine if a 16 bit odd
314 * We end the list with the value 1. Thus, loops of the form:
317 * unsigned short *tp;
319 * for (isqr=fsqrt(n), tp=prime; (*tp <= isqr) && (n % *tp); ++tp) {
322 * will terminate because *tp == 1 and thus (n % *tp) == 0. To determine if
323 * a factor was found, one must:
325 * if (*tp <= isqr && *tp != 1) {
326 * *tp is a factor of n
329 CONST
unsigned short prime
[MAP_POPCNT
+1] = {
330 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
331 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
332 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
333 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331,
334 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,
335 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
336 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613,
337 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709,
338 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821,
339 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
340 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019,
341 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093,
342 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187,
343 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
344 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367,
345 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
346 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543,
347 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613,
348 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709,
349 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801,
350 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901,
351 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999,
352 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087,
353 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179,
354 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281,
355 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371,
356 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447,
357 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557,
358 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671,
359 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731,
360 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833,
361 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927,
362 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037,
363 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163,
364 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253,
365 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343,
366 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457,
367 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539,
368 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623,
369 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719,
370 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823,
371 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919,
372 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019,
373 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127,
374 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229,
375 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327,
376 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441,
377 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523,
378 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643,
379 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733,
380 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861,
381 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957,
382 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039,
383 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153,
384 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273,
385 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393,
386 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477,
387 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569,
388 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669,
389 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783,
390 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861,
391 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987,
392 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091,
393 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203,
394 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299,
395 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373,
396 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521,
397 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619,
398 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719,
399 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829,
400 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
401 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019,
402 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151,
403 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247,
404 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393,
405 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507,
406 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583,
407 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687,
408 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793,
409 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907,
410 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039,
411 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147,
412 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243,
413 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363,
414 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467,
415 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599,
416 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693,
417 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783,
418 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887,
419 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007,
420 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127,
421 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221,
422 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337,
423 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431,
424 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521,
425 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643,
426 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749,
427 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851,
428 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949,
429 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091,
430 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169,
431 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271,
432 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357,
433 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477,
434 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601,
435 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691,
436 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799,
437 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903,
438 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027,
439 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119,
440 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243,
441 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329,
442 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447,
443 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551,
444 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689,
445 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801,
446 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897,
447 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971,
448 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097,
449 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197,
450 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281,
451 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
452 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491,
453 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577,
454 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659,
455 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781,
456 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899,
457 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979,
458 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093,
459 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177,
460 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297,
461 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411,
462 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513,
463 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633,
464 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721,
465 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829,
466 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913,
467 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033,
468 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159,
469 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303,
470 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411,
471 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519,
472 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621,
473 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717,
474 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783,
475 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887,
476 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013,
477 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121,
478 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227,
479 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307,
480 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391,
481 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497,
482 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619,
483 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727,
484 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797,
485 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907,
486 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033,
487 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111,
488 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231,
489 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363,
490 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477,
491 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
492 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693,
493 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829,
494 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931,
495 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029,
496 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123, 17137,
497 17159, 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257,
498 17291, 17293, 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377,
499 17383, 17387, 17389, 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
500 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539, 17551, 17569,
501 17573, 17579, 17581, 17597, 17599, 17609, 17623, 17627, 17657, 17659, 17669,
502 17681, 17683, 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789,
503 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881, 17891, 17903, 17909,
504 17911, 17921, 17923, 17929, 17939, 17957, 17959, 17971, 17977, 17981, 17987,
505 17989, 18013, 18041, 18043, 18047, 18049, 18059, 18061, 18077, 18089, 18097,
506 18119, 18121, 18127, 18131, 18133, 18143, 18149, 18169, 18181, 18191, 18199,
507 18211, 18217, 18223, 18229, 18233, 18251, 18253, 18257, 18269, 18287, 18289,
508 18301, 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371, 18379, 18397,
509 18401, 18413, 18427, 18433, 18439, 18443, 18451, 18457, 18461, 18481, 18493,
510 18503, 18517, 18521, 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617,
511 18637, 18661, 18671, 18679, 18691, 18701, 18713, 18719, 18731, 18743, 18749,
512 18757, 18773, 18787, 18793, 18797, 18803, 18839, 18859, 18869, 18899, 18911,
513 18913, 18917, 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013, 19031,
514 19037, 19051, 19069, 19073, 19079, 19081, 19087, 19121, 19139, 19141, 19157,
515 19163, 19181, 19183, 19207, 19211, 19213, 19219, 19231, 19237, 19249, 19259,
516 19267, 19273, 19289, 19301, 19309, 19319, 19333, 19373, 19379, 19381, 19387,
517 19391, 19403, 19417, 19421, 19423, 19427, 19429, 19433, 19441, 19447, 19457,
518 19463, 19469, 19471, 19477, 19483, 19489, 19501, 19507, 19531, 19541, 19543,
519 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609, 19661, 19681, 19687,
520 19697, 19699, 19709, 19717, 19727, 19739, 19751, 19753, 19759, 19763, 19777,
521 19793, 19801, 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889, 19891,
522 19913, 19919, 19927, 19937, 19949, 19961, 19963, 19973, 19979, 19991, 19993,
523 19997, 20011, 20021, 20023, 20029, 20047, 20051, 20063, 20071, 20089, 20101,
524 20107, 20113, 20117, 20123, 20129, 20143, 20147, 20149, 20161, 20173, 20177,
525 20183, 20201, 20219, 20231, 20233, 20249, 20261, 20269, 20287, 20297, 20323,
526 20327, 20333, 20341, 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399,
527 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483, 20507, 20509, 20521,
528 20533, 20543, 20549, 20551, 20563, 20593, 20599, 20611, 20627, 20639, 20641,
529 20663, 20681, 20693, 20707, 20717, 20719, 20731, 20743, 20747, 20749, 20753,
530 20759, 20771, 20773, 20789, 20807, 20809, 20849, 20857, 20873, 20879, 20887,
531 20897, 20899, 20903, 20921, 20929, 20939, 20947, 20959, 20963, 20981, 20983,
532 21001, 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061, 21067, 21089,
533 21101, 21107, 21121, 21139, 21143, 21149, 21157, 21163, 21169, 21179, 21187,
534 21191, 21193, 21211, 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317,
535 21319, 21323, 21341, 21347, 21377, 21379, 21383, 21391, 21397, 21401, 21407,
536 21419, 21433, 21467, 21481, 21487, 21491, 21493, 21499, 21503, 21517, 21521,
537 21523, 21529, 21557, 21559, 21563, 21569, 21577, 21587, 21589, 21599, 21601,
538 21611, 21613, 21617, 21647, 21649, 21661, 21673, 21683, 21701, 21713, 21727,
539 21737, 21739, 21751, 21757, 21767, 21773, 21787, 21799, 21803, 21817, 21821,
540 21839, 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911, 21929, 21937,
541 21943, 21961, 21977, 21991, 21997, 22003, 22013, 22027, 22031, 22037, 22039,
542 22051, 22063, 22067, 22073, 22079, 22091, 22093, 22109, 22111, 22123, 22129,
543 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193, 22229, 22247, 22259,
544 22271, 22273, 22277, 22279, 22283, 22291, 22303, 22307, 22343, 22349, 22367,
545 22369, 22381, 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469, 22481,
546 22483, 22501, 22511, 22531, 22541, 22543, 22549, 22567, 22571, 22573, 22613,
547 22619, 22621, 22637, 22639, 22643, 22651, 22669, 22679, 22691, 22697, 22699,
548 22709, 22717, 22721, 22727, 22739, 22741, 22751, 22769, 22777, 22783, 22787,
549 22807, 22811, 22817, 22853, 22859, 22861, 22871, 22877, 22901, 22907, 22921,
550 22937, 22943, 22961, 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027,
551 23029, 23039, 23041, 23053, 23057, 23059, 23063, 23071, 23081, 23087, 23099,
552 23117, 23131, 23143, 23159, 23167, 23173, 23189, 23197, 23201, 23203, 23209,
553 23227, 23251, 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327, 23333,
554 23339, 23357, 23369, 23371, 23399, 23417, 23431, 23447, 23459, 23473, 23497,
555 23509, 23531, 23537, 23539, 23549, 23557, 23561, 23563, 23567, 23581, 23593,
556 23599, 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669, 23671, 23677,
557 23687, 23689, 23719, 23741, 23743, 23747, 23753, 23761, 23767, 23773, 23789,
558 23801, 23813, 23819, 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887,
559 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971, 23977, 23981, 23993,
560 24001, 24007, 24019, 24023, 24029, 24043, 24049, 24061, 24071, 24077, 24083,
561 24091, 24097, 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151, 24169,
562 24179, 24181, 24197, 24203, 24223, 24229, 24239, 24247, 24251, 24281, 24317,
563 24329, 24337, 24359, 24371, 24373, 24379, 24391, 24407, 24413, 24419, 24421,
564 24439, 24443, 24469, 24473, 24481, 24499, 24509, 24517, 24527, 24533, 24547,
565 24551, 24571, 24593, 24611, 24623, 24631, 24659, 24671, 24677, 24683, 24691,
566 24697, 24709, 24733, 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821,
567 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917, 24919, 24923, 24943,
568 24953, 24967, 24971, 24977, 24979, 24989, 25013, 25031, 25033, 25037, 25057,
569 25073, 25087, 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163, 25169,
570 25171, 25183, 25189, 25219, 25229, 25237, 25243, 25247, 25253, 25261, 25301,
571 25303, 25307, 25309, 25321, 25339, 25343, 25349, 25357, 25367, 25373, 25391,
572 25409, 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469, 25471, 25523,
573 25537, 25541, 25561, 25577, 25579, 25583, 25589, 25601, 25603, 25609, 25621,
574 25633, 25639, 25643, 25657, 25667, 25673, 25679, 25693, 25703, 25717, 25733,
575 25741, 25747, 25759, 25763, 25771, 25793, 25799, 25801, 25819, 25841, 25847,
576 25849, 25867, 25873, 25889, 25903, 25913, 25919, 25931, 25933, 25939, 25943,
577 25951, 25969, 25981, 25997, 25999, 26003, 26017, 26021, 26029, 26041, 26053,
578 26083, 26099, 26107, 26111, 26113, 26119, 26141, 26153, 26161, 26171, 26177,
579 26183, 26189, 26203, 26209, 26227, 26237, 26249, 26251, 26261, 26263, 26267,
580 26293, 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371, 26387, 26393,
581 26399, 26407, 26417, 26423, 26431, 26437, 26449, 26459, 26479, 26489, 26497,
582 26501, 26513, 26539, 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641,
583 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701, 26711, 26713, 26717,
584 26723, 26729, 26731, 26737, 26759, 26777, 26783, 26801, 26813, 26821, 26833,
585 26839, 26849, 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921, 26927,
586 26947, 26951, 26953, 26959, 26981, 26987, 26993, 27011, 27017, 27031, 27043,
587 27059, 27061, 27067, 27073, 27077, 27091, 27103, 27107, 27109, 27127, 27143,
588 27179, 27191, 27197, 27211, 27239, 27241, 27253, 27259, 27271, 27277, 27281,
589 27283, 27299, 27329, 27337, 27361, 27367, 27397, 27407, 27409, 27427, 27431,
590 27437, 27449, 27457, 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541,
591 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653, 27673, 27689, 27691,
592 27697, 27701, 27733, 27737, 27739, 27743, 27749, 27751, 27763, 27767, 27773,
593 27779, 27791, 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847, 27851,
594 27883, 27893, 27901, 27917, 27919, 27941, 27943, 27947, 27953, 27961, 27967,
595 27983, 27997, 28001, 28019, 28027, 28031, 28051, 28057, 28069, 28081, 28087,
596 28097, 28099, 28109, 28111, 28123, 28151, 28163, 28181, 28183, 28201, 28211,
597 28219, 28229, 28277, 28279, 28283, 28289, 28297, 28307, 28309, 28319, 28349,
598 28351, 28387, 28393, 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463,
599 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547, 28549, 28559, 28571,
600 28573, 28579, 28591, 28597, 28603, 28607, 28619, 28621, 28627, 28631, 28643,
601 28649, 28657, 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723, 28729,
602 28751, 28753, 28759, 28771, 28789, 28793, 28807, 28813, 28817, 28837, 28843,
603 28859, 28867, 28871, 28879, 28901, 28909, 28921, 28927, 28933, 28949, 28961,
604 28979, 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063, 29077, 29101,
605 29123, 29129, 29131, 29137, 29147, 29153, 29167, 29173, 29179, 29191, 29201,
606 29207, 29209, 29221, 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311,
607 29327, 29333, 29339, 29347, 29363, 29383, 29387, 29389, 29399, 29401, 29411,
608 29423, 29429, 29437, 29443, 29453, 29473, 29483, 29501, 29527, 29531, 29537,
609 29567, 29569, 29573, 29581, 29587, 29599, 29611, 29629, 29633, 29641, 29663,
610 29669, 29671, 29683, 29717, 29723, 29741, 29753, 29759, 29761, 29789, 29803,
611 29819, 29833, 29837, 29851, 29863, 29867, 29873, 29879, 29881, 29917, 29921,
612 29927, 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047, 30059, 30071,
613 30089, 30091, 30097, 30103, 30109, 30113, 30119, 30133, 30137, 30139, 30161,
614 30169, 30181, 30187, 30197, 30203, 30211, 30223, 30241, 30253, 30259, 30269,
615 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347, 30367, 30389, 30391,
616 30403, 30427, 30431, 30449, 30467, 30469, 30491, 30493, 30497, 30509, 30517,
617 30529, 30539, 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643, 30649,
618 30661, 30671, 30677, 30689, 30697, 30703, 30707, 30713, 30727, 30757, 30763,
619 30773, 30781, 30803, 30809, 30817, 30829, 30839, 30841, 30851, 30853, 30859,
620 30869, 30871, 30881, 30893, 30911, 30931, 30937, 30941, 30949, 30971, 30977,
621 30983, 31013, 31019, 31033, 31039, 31051, 31063, 31069, 31079, 31081, 31091,
622 31121, 31123, 31139, 31147, 31151, 31153, 31159, 31177, 31181, 31183, 31189,
623 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253, 31259, 31267, 31271,
624 31277, 31307, 31319, 31321, 31327, 31333, 31337, 31357, 31379, 31387, 31391,
625 31393, 31397, 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531, 31541,
626 31543, 31547, 31567, 31573, 31583, 31601, 31607, 31627, 31643, 31649, 31657,
627 31663, 31667, 31687, 31699, 31721, 31723, 31727, 31729, 31741, 31751, 31769,
628 31771, 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883, 31891, 31907,
629 31957, 31963, 31973, 31981, 31991, 32003, 32009, 32027, 32029, 32051, 32057,
630 32059, 32063, 32069, 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143,
631 32159, 32173, 32183, 32189, 32191, 32203, 32213, 32233, 32237, 32251, 32257,
632 32261, 32297, 32299, 32303, 32309, 32321, 32323, 32327, 32341, 32353, 32359,
633 32363, 32369, 32371, 32377, 32381, 32401, 32411, 32413, 32423, 32429, 32441,
634 32443, 32467, 32479, 32491, 32497, 32503, 32507, 32531, 32533, 32537, 32561,
635 32563, 32569, 32573, 32579, 32587, 32603, 32609, 32611, 32621, 32633, 32647,
636 32653, 32687, 32693, 32707, 32713, 32717, 32719, 32749, 32771, 32779, 32783,
637 32789, 32797, 32801, 32803, 32831, 32833, 32839, 32843, 32869, 32887, 32909,
638 32911, 32917, 32933, 32939, 32941, 32957, 32969, 32971, 32983, 32987, 32993,
639 32999, 33013, 33023, 33029, 33037, 33049, 33053, 33071, 33073, 33083, 33091,
640 33107, 33113, 33119, 33149, 33151, 33161, 33179, 33181, 33191, 33199, 33203,
641 33211, 33223, 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331, 33343,
642 33347, 33349, 33353, 33359, 33377, 33391, 33403, 33409, 33413, 33427, 33457,
643 33461, 33469, 33479, 33487, 33493, 33503, 33521, 33529, 33533, 33547, 33563,
644 33569, 33577, 33581, 33587, 33589, 33599, 33601, 33613, 33617, 33619, 33623,
645 33629, 33637, 33641, 33647, 33679, 33703, 33713, 33721, 33739, 33749, 33751,
646 33757, 33767, 33769, 33773, 33791, 33797, 33809, 33811, 33827, 33829, 33851,
647 33857, 33863, 33871, 33889, 33893, 33911, 33923, 33931, 33937, 33941, 33961,
648 33967, 33997, 34019, 34031, 34033, 34039, 34057, 34061, 34123, 34127, 34129,
649 34141, 34147, 34157, 34159, 34171, 34183, 34211, 34213, 34217, 34231, 34253,
650 34259, 34261, 34267, 34273, 34283, 34297, 34301, 34303, 34313, 34319, 34327,
651 34337, 34351, 34361, 34367, 34369, 34381, 34403, 34421, 34429, 34439, 34457,
652 34469, 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519, 34537, 34543,
653 34549, 34583, 34589, 34591, 34603, 34607, 34613, 34631, 34649, 34651, 34667,
654 34673, 34679, 34687, 34693, 34703, 34721, 34729, 34739, 34747, 34757, 34759,
655 34763, 34781, 34807, 34819, 34841, 34843, 34847, 34849, 34871, 34877, 34883,
656 34897, 34913, 34919, 34939, 34949, 34961, 34963, 34981, 35023, 35027, 35051,
657 35053, 35059, 35069, 35081, 35083, 35089, 35099, 35107, 35111, 35117, 35129,
658 35141, 35149, 35153, 35159, 35171, 35201, 35221, 35227, 35251, 35257, 35267,
659 35279, 35281, 35291, 35311, 35317, 35323, 35327, 35339, 35353, 35363, 35381,
660 35393, 35401, 35407, 35419, 35423, 35437, 35447, 35449, 35461, 35491, 35507,
661 35509, 35521, 35527, 35531, 35533, 35537, 35543, 35569, 35573, 35591, 35593,
662 35597, 35603, 35617, 35671, 35677, 35729, 35731, 35747, 35753, 35759, 35771,
663 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851, 35863, 35869, 35879,
664 35897, 35899, 35911, 35923, 35933, 35951, 35963, 35969, 35977, 35983, 35993,
665 35999, 36007, 36011, 36013, 36017, 36037, 36061, 36067, 36073, 36083, 36097,
666 36107, 36109, 36131, 36137, 36151, 36161, 36187, 36191, 36209, 36217, 36229,
667 36241, 36251, 36263, 36269, 36277, 36293, 36299, 36307, 36313, 36319, 36341,
668 36343, 36353, 36373, 36383, 36389, 36433, 36451, 36457, 36467, 36469, 36473,
669 36479, 36493, 36497, 36523, 36527, 36529, 36541, 36551, 36559, 36563, 36571,
670 36583, 36587, 36599, 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683,
671 36691, 36697, 36709, 36713, 36721, 36739, 36749, 36761, 36767, 36779, 36781,
672 36787, 36791, 36793, 36809, 36821, 36833, 36847, 36857, 36871, 36877, 36887,
673 36899, 36901, 36913, 36919, 36923, 36929, 36931, 36943, 36947, 36973, 36979,
674 36997, 37003, 37013, 37019, 37021, 37039, 37049, 37057, 37061, 37087, 37097,
675 37117, 37123, 37139, 37159, 37171, 37181, 37189, 37199, 37201, 37217, 37223,
676 37243, 37253, 37273, 37277, 37307, 37309, 37313, 37321, 37337, 37339, 37357,
677 37361, 37363, 37369, 37379, 37397, 37409, 37423, 37441, 37447, 37463, 37483,
678 37489, 37493, 37501, 37507, 37511, 37517, 37529, 37537, 37547, 37549, 37561,
679 37567, 37571, 37573, 37579, 37589, 37591, 37607, 37619, 37633, 37643, 37649,
680 37657, 37663, 37691, 37693, 37699, 37717, 37747, 37781, 37783, 37799, 37811,
681 37813, 37831, 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907, 37951,
682 37957, 37963, 37967, 37987, 37991, 37993, 37997, 38011, 38039, 38047, 38053,
683 38069, 38083, 38113, 38119, 38149, 38153, 38167, 38177, 38183, 38189, 38197,
684 38201, 38219, 38231, 38237, 38239, 38261, 38273, 38281, 38287, 38299, 38303,
685 38317, 38321, 38327, 38329, 38333, 38351, 38371, 38377, 38393, 38431, 38447,
686 38449, 38453, 38459, 38461, 38501, 38543, 38557, 38561, 38567, 38569, 38593,
687 38603, 38609, 38611, 38629, 38639, 38651, 38653, 38669, 38671, 38677, 38693,
688 38699, 38707, 38711, 38713, 38723, 38729, 38737, 38747, 38749, 38767, 38783,
689 38791, 38803, 38821, 38833, 38839, 38851, 38861, 38867, 38873, 38891, 38903,
690 38917, 38921, 38923, 38933, 38953, 38959, 38971, 38977, 38993, 39019, 39023,
691 39041, 39043, 39047, 39079, 39089, 39097, 39103, 39107, 39113, 39119, 39133,
692 39139, 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217, 39227, 39229,
693 39233, 39239, 39241, 39251, 39293, 39301, 39313, 39317, 39323, 39341, 39343,
694 39359, 39367, 39371, 39373, 39383, 39397, 39409, 39419, 39439, 39443, 39451,
695 39461, 39499, 39503, 39509, 39511, 39521, 39541, 39551, 39563, 39569, 39581,
696 39607, 39619, 39623, 39631, 39659, 39667, 39671, 39679, 39703, 39709, 39719,
697 39727, 39733, 39749, 39761, 39769, 39779, 39791, 39799, 39821, 39827, 39829,
698 39839, 39841, 39847, 39857, 39863, 39869, 39877, 39883, 39887, 39901, 39929,
699 39937, 39953, 39971, 39979, 39983, 39989, 40009, 40013, 40031, 40037, 40039,
700 40063, 40087, 40093, 40099, 40111, 40123, 40127, 40129, 40151, 40153, 40163,
701 40169, 40177, 40189, 40193, 40213, 40231, 40237, 40241, 40253, 40277, 40283,
702 40289, 40343, 40351, 40357, 40361, 40387, 40423, 40427, 40429, 40433, 40459,
703 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529, 40531, 40543, 40559,
704 40577, 40583, 40591, 40597, 40609, 40627, 40637, 40639, 40693, 40697, 40699,
705 40709, 40739, 40751, 40759, 40763, 40771, 40787, 40801, 40813, 40819, 40823,
706 40829, 40841, 40847, 40849, 40853, 40867, 40879, 40883, 40897, 40903, 40927,
707 40933, 40939, 40949, 40961, 40973, 40993, 41011, 41017, 41023, 41039, 41047,
708 41051, 41057, 41077, 41081, 41113, 41117, 41131, 41141, 41143, 41149, 41161,
709 41177, 41179, 41183, 41189, 41201, 41203, 41213, 41221, 41227, 41231, 41233,
710 41243, 41257, 41263, 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381,
711 41387, 41389, 41399, 41411, 41413, 41443, 41453, 41467, 41479, 41491, 41507,
712 41513, 41519, 41521, 41539, 41543, 41549, 41579, 41593, 41597, 41603, 41609,
713 41611, 41617, 41621, 41627, 41641, 41647, 41651, 41659, 41669, 41681, 41687,
714 41719, 41729, 41737, 41759, 41761, 41771, 41777, 41801, 41809, 41813, 41843,
715 41849, 41851, 41863, 41879, 41887, 41893, 41897, 41903, 41911, 41927, 41941,
716 41947, 41953, 41957, 41959, 41969, 41981, 41983, 41999, 42013, 42017, 42019,
717 42023, 42043, 42061, 42071, 42073, 42083, 42089, 42101, 42131, 42139, 42157,
718 42169, 42179, 42181, 42187, 42193, 42197, 42209, 42221, 42223, 42227, 42239,
719 42257, 42281, 42283, 42293, 42299, 42307, 42323, 42331, 42337, 42349, 42359,
720 42373, 42379, 42391, 42397, 42403, 42407, 42409, 42433, 42437, 42443, 42451,
721 42457, 42461, 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533, 42557,
722 42569, 42571, 42577, 42589, 42611, 42641, 42643, 42649, 42667, 42677, 42683,
723 42689, 42697, 42701, 42703, 42709, 42719, 42727, 42737, 42743, 42751, 42767,
724 42773, 42787, 42793, 42797, 42821, 42829, 42839, 42841, 42853, 42859, 42863,
725 42899, 42901, 42923, 42929, 42937, 42943, 42953, 42961, 42967, 42979, 42989,
726 43003, 43013, 43019, 43037, 43049, 43051, 43063, 43067, 43093, 43103, 43117,
727 43133, 43151, 43159, 43177, 43189, 43201, 43207, 43223, 43237, 43261, 43271,
728 43283, 43291, 43313, 43319, 43321, 43331, 43391, 43397, 43399, 43403, 43411,
729 43427, 43441, 43451, 43457, 43481, 43487, 43499, 43517, 43541, 43543, 43573,
730 43577, 43579, 43591, 43597, 43607, 43609, 43613, 43627, 43633, 43649, 43651,
731 43661, 43669, 43691, 43711, 43717, 43721, 43753, 43759, 43777, 43781, 43783,
732 43787, 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913, 43933, 43943,
733 43951, 43961, 43963, 43969, 43973, 43987, 43991, 43997, 44017, 44021, 44027,
734 44029, 44041, 44053, 44059, 44071, 44087, 44089, 44101, 44111, 44119, 44123,
735 44129, 44131, 44159, 44171, 44179, 44189, 44201, 44203, 44207, 44221, 44249,
736 44257, 44263, 44267, 44269, 44273, 44279, 44281, 44293, 44351, 44357, 44371,
737 44381, 44383, 44389, 44417, 44449, 44453, 44483, 44491, 44497, 44501, 44507,
738 44519, 44531, 44533, 44537, 44543, 44549, 44563, 44579, 44587, 44617, 44621,
739 44623, 44633, 44641, 44647, 44651, 44657, 44683, 44687, 44699, 44701, 44711,
740 44729, 44741, 44753, 44771, 44773, 44777, 44789, 44797, 44809, 44819, 44839,
741 44843, 44851, 44867, 44879, 44887, 44893, 44909, 44917, 44927, 44939, 44953,
742 44959, 44963, 44971, 44983, 44987, 45007, 45013, 45053, 45061, 45077, 45083,
743 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179, 45181, 45191, 45197,
744 45233, 45247, 45259, 45263, 45281, 45289, 45293, 45307, 45317, 45319, 45329,
745 45337, 45341, 45343, 45361, 45377, 45389, 45403, 45413, 45427, 45433, 45439,
746 45481, 45491, 45497, 45503, 45523, 45533, 45541, 45553, 45557, 45569, 45587,
747 45589, 45599, 45613, 45631, 45641, 45659, 45667, 45673, 45677, 45691, 45697,
748 45707, 45737, 45751, 45757, 45763, 45767, 45779, 45817, 45821, 45823, 45827,
749 45833, 45841, 45853, 45863, 45869, 45887, 45893, 45943, 45949, 45953, 45959,
750 45971, 45979, 45989, 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093,
751 46099, 46103, 46133, 46141, 46147, 46153, 46171, 46181, 46183, 46187, 46199,
752 46219, 46229, 46237, 46261, 46271, 46273, 46279, 46301, 46307, 46309, 46327,
753 46337, 46349, 46351, 46381, 46399, 46411, 46439, 46441, 46447, 46451, 46457,
754 46471, 46477, 46489, 46499, 46507, 46511, 46523, 46549, 46559, 46567, 46573,
755 46589, 46591, 46601, 46619, 46633, 46639, 46643, 46649, 46663, 46679, 46681,
756 46687, 46691, 46703, 46723, 46727, 46747, 46751, 46757, 46769, 46771, 46807,
757 46811, 46817, 46819, 46829, 46831, 46853, 46861, 46867, 46877, 46889, 46901,
758 46919, 46933, 46957, 46993, 46997, 47017, 47041, 47051, 47057, 47059, 47087,
759 47093, 47111, 47119, 47123, 47129, 47137, 47143, 47147, 47149, 47161, 47189,
760 47207, 47221, 47237, 47251, 47269, 47279, 47287, 47293, 47297, 47303, 47309,
761 47317, 47339, 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417, 47419,
762 47431, 47441, 47459, 47491, 47497, 47501, 47507, 47513, 47521, 47527, 47533,
763 47543, 47563, 47569, 47581, 47591, 47599, 47609, 47623, 47629, 47639, 47653,
764 47657, 47659, 47681, 47699, 47701, 47711, 47713, 47717, 47737, 47741, 47743,
765 47777, 47779, 47791, 47797, 47807, 47809, 47819, 47837, 47843, 47857, 47869,
766 47881, 47903, 47911, 47917, 47933, 47939, 47947, 47951, 47963, 47969, 47977,
767 47981, 48017, 48023, 48029, 48049, 48073, 48079, 48091, 48109, 48119, 48121,
768 48131, 48157, 48163, 48179, 48187, 48193, 48197, 48221, 48239, 48247, 48259,
769 48271, 48281, 48299, 48311, 48313, 48337, 48341, 48353, 48371, 48383, 48397,
770 48407, 48409, 48413, 48437, 48449, 48463, 48473, 48479, 48481, 48487, 48491,
771 48497, 48523, 48527, 48533, 48539, 48541, 48563, 48571, 48589, 48593, 48611,
772 48619, 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731, 48733, 48751,
773 48757, 48761, 48767, 48779, 48781, 48787, 48799, 48809, 48817, 48821, 48823,
774 48847, 48857, 48859, 48869, 48871, 48883, 48889, 48907, 48947, 48953, 48973,
775 48989, 48991, 49003, 49009, 49019, 49031, 49033, 49037, 49043, 49057, 49069,
776 49081, 49103, 49109, 49117, 49121, 49123, 49139, 49157, 49169, 49171, 49177,
777 49193, 49199, 49201, 49207, 49211, 49223, 49253, 49261, 49277, 49279, 49297,
778 49307, 49331, 49333, 49339, 49363, 49367, 49369, 49391, 49393, 49409, 49411,
779 49417, 49429, 49433, 49451, 49459, 49463, 49477, 49481, 49499, 49523, 49529,
780 49531, 49537, 49547, 49549, 49559, 49597, 49603, 49613, 49627, 49633, 49639,
781 49663, 49667, 49669, 49681, 49697, 49711, 49727, 49739, 49741, 49747, 49757,
782 49783, 49787, 49789, 49801, 49807, 49811, 49823, 49831, 49843, 49853, 49871,
783 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943, 49957, 49991, 49993,
784 49999, 50021, 50023, 50033, 50047, 50051, 50053, 50069, 50077, 50087, 50093,
785 50101, 50111, 50119, 50123, 50129, 50131, 50147, 50153, 50159, 50177, 50207,
786 50221, 50227, 50231, 50261, 50263, 50273, 50287, 50291, 50311, 50321, 50329,
787 50333, 50341, 50359, 50363, 50377, 50383, 50387, 50411, 50417, 50423, 50441,
788 50459, 50461, 50497, 50503, 50513, 50527, 50539, 50543, 50549, 50551, 50581,
789 50587, 50591, 50593, 50599, 50627, 50647, 50651, 50671, 50683, 50707, 50723,
790 50741, 50753, 50767, 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857,
791 50867, 50873, 50891, 50893, 50909, 50923, 50929, 50951, 50957, 50969, 50971,
792 50989, 50993, 51001, 51031, 51043, 51047, 51059, 51061, 51071, 51109, 51131,
793 51133, 51137, 51151, 51157, 51169, 51193, 51197, 51199, 51203, 51217, 51229,
794 51239, 51241, 51257, 51263, 51283, 51287, 51307, 51329, 51341, 51343, 51347,
795 51349, 51361, 51383, 51407, 51413, 51419, 51421, 51427, 51431, 51437, 51439,
796 51449, 51461, 51473, 51479, 51481, 51487, 51503, 51511, 51517, 51521, 51539,
797 51551, 51563, 51577, 51581, 51593, 51599, 51607, 51613, 51631, 51637, 51647,
798 51659, 51673, 51679, 51683, 51691, 51713, 51719, 51721, 51749, 51767, 51769,
799 51787, 51797, 51803, 51817, 51827, 51829, 51839, 51853, 51859, 51869, 51871,
800 51893, 51899, 51907, 51913, 51929, 51941, 51949, 51971, 51973, 51977, 51991,
801 52009, 52021, 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121, 52127,
802 52147, 52153, 52163, 52177, 52181, 52183, 52189, 52201, 52223, 52237, 52249,
803 52253, 52259, 52267, 52289, 52291, 52301, 52313, 52321, 52361, 52363, 52369,
804 52379, 52387, 52391, 52433, 52453, 52457, 52489, 52501, 52511, 52517, 52529,
805 52541, 52543, 52553, 52561, 52567, 52571, 52579, 52583, 52609, 52627, 52631,
806 52639, 52667, 52673, 52691, 52697, 52709, 52711, 52721, 52727, 52733, 52747,
807 52757, 52769, 52783, 52807, 52813, 52817, 52837, 52859, 52861, 52879, 52883,
808 52889, 52901, 52903, 52919, 52937, 52951, 52957, 52963, 52967, 52973, 52981,
809 52999, 53003, 53017, 53047, 53051, 53069, 53077, 53087, 53089, 53093, 53101,
810 53113, 53117, 53129, 53147, 53149, 53161, 53171, 53173, 53189, 53197, 53201,
811 53231, 53233, 53239, 53267, 53269, 53279, 53281, 53299, 53309, 53323, 53327,
812 53353, 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437, 53441, 53453,
813 53479, 53503, 53507, 53527, 53549, 53551, 53569, 53591, 53593, 53597, 53609,
814 53611, 53617, 53623, 53629, 53633, 53639, 53653, 53657, 53681, 53693, 53699,
815 53717, 53719, 53731, 53759, 53773, 53777, 53783, 53791, 53813, 53819, 53831,
816 53849, 53857, 53861, 53881, 53887, 53891, 53897, 53899, 53917, 53923, 53927,
817 53939, 53951, 53959, 53987, 53993, 54001, 54011, 54013, 54037, 54049, 54059,
818 54083, 54091, 54101, 54121, 54133, 54139, 54151, 54163, 54167, 54181, 54193,
819 54217, 54251, 54269, 54277, 54287, 54293, 54311, 54319, 54323, 54331, 54347,
820 54361, 54367, 54371, 54377, 54401, 54403, 54409, 54413, 54419, 54421, 54437,
821 54443, 54449, 54469, 54493, 54497, 54499, 54503, 54517, 54521, 54539, 54541,
822 54547, 54559, 54563, 54577, 54581, 54583, 54601, 54617, 54623, 54629, 54631,
823 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727, 54751, 54767, 54773,
824 54779, 54787, 54799, 54829, 54833, 54851, 54869, 54877, 54881, 54907, 54917,
825 54919, 54941, 54949, 54959, 54973, 54979, 54983, 55001, 55009, 55021, 55049,
826 55051, 55057, 55061, 55073, 55079, 55103, 55109, 55117, 55127, 55147, 55163,
827 55171, 55201, 55207, 55213, 55217, 55219, 55229, 55243, 55249, 55259, 55291,
828 55313, 55331, 55333, 55337, 55339, 55343, 55351, 55373, 55381, 55399, 55411,
829 55439, 55441, 55457, 55469, 55487, 55501, 55511, 55529, 55541, 55547, 55579,
830 55589, 55603, 55609, 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667,
831 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733, 55763, 55787, 55793,
832 55799, 55807, 55813, 55817, 55819, 55823, 55829, 55837, 55843, 55849, 55871,
833 55889, 55897, 55901, 55903, 55921, 55927, 55931, 55933, 55949, 55967, 55987,
834 55997, 56003, 56009, 56039, 56041, 56053, 56081, 56087, 56093, 56099, 56101,
835 56113, 56123, 56131, 56149, 56167, 56171, 56179, 56197, 56207, 56209, 56237,
836 56239, 56249, 56263, 56267, 56269, 56299, 56311, 56333, 56359, 56369, 56377,
837 56383, 56393, 56401, 56417, 56431, 56437, 56443, 56453, 56467, 56473, 56477,
838 56479, 56489, 56501, 56503, 56509, 56519, 56527, 56531, 56533, 56543, 56569,
839 56591, 56597, 56599, 56611, 56629, 56633, 56659, 56663, 56671, 56681, 56687,
840 56701, 56711, 56713, 56731, 56737, 56747, 56767, 56773, 56779, 56783, 56807,
841 56809, 56813, 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897, 56909,
842 56911, 56921, 56923, 56929, 56941, 56951, 56957, 56963, 56983, 56989, 56993,
843 56999, 57037, 57041, 57047, 57059, 57073, 57077, 57089, 57097, 57107, 57119,
844 57131, 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193, 57203, 57221,
845 57223, 57241, 57251, 57259, 57269, 57271, 57283, 57287, 57301, 57329, 57331,
846 57347, 57349, 57367, 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467,
847 57487, 57493, 57503, 57527, 57529, 57557, 57559, 57571, 57587, 57593, 57601,
848 57637, 57641, 57649, 57653, 57667, 57679, 57689, 57697, 57709, 57713, 57719,
849 57727, 57731, 57737, 57751, 57773, 57781, 57787, 57791, 57793, 57803, 57809,
850 57829, 57839, 57847, 57853, 57859, 57881, 57899, 57901, 57917, 57923, 57943,
851 57947, 57973, 57977, 57991, 58013, 58027, 58031, 58043, 58049, 58057, 58061,
852 58067, 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153, 58169, 58171,
853 58189, 58193, 58199, 58207, 58211, 58217, 58229, 58231, 58237, 58243, 58271,
854 58309, 58313, 58321, 58337, 58363, 58367, 58369, 58379, 58391, 58393, 58403,
855 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477, 58481, 58511, 58537,
856 58543, 58549, 58567, 58573, 58579, 58601, 58603, 58613, 58631, 58657, 58661,
857 58679, 58687, 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763, 58771,
858 58787, 58789, 58831, 58889, 58897, 58901, 58907, 58909, 58913, 58921, 58937,
859 58943, 58963, 58967, 58979, 58991, 58997, 59009, 59011, 59021, 59023, 59029,
860 59051, 59053, 59063, 59069, 59077, 59083, 59093, 59107, 59113, 59119, 59123,
861 59141, 59149, 59159, 59167, 59183, 59197, 59207, 59209, 59219, 59221, 59233,
862 59239, 59243, 59263, 59273, 59281, 59333, 59341, 59351, 59357, 59359, 59369,
863 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441, 59443, 59447, 59453,
864 59467, 59471, 59473, 59497, 59509, 59513, 59539, 59557, 59561, 59567, 59581,
865 59611, 59617, 59621, 59627, 59629, 59651, 59659, 59663, 59669, 59671, 59693,
866 59699, 59707, 59723, 59729, 59743, 59747, 59753, 59771, 59779, 59791, 59797,
867 59809, 59833, 59863, 59879, 59887, 59921, 59929, 59951, 59957, 59971, 59981,
868 59999, 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089, 60091, 60101,
869 60103, 60107, 60127, 60133, 60139, 60149, 60161, 60167, 60169, 60209, 60217,
870 60223, 60251, 60257, 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343,
871 60353, 60373, 60383, 60397, 60413, 60427, 60443, 60449, 60457, 60493, 60497,
872 60509, 60521, 60527, 60539, 60589, 60601, 60607, 60611, 60617, 60623, 60631,
873 60637, 60647, 60649, 60659, 60661, 60679, 60689, 60703, 60719, 60727, 60733,
874 60737, 60757, 60761, 60763, 60773, 60779, 60793, 60811, 60821, 60859, 60869,
875 60887, 60889, 60899, 60901, 60913, 60917, 60919, 60923, 60937, 60943, 60953,
876 60961, 61001, 61007, 61027, 61031, 61043, 61051, 61057, 61091, 61099, 61121,
877 61129, 61141, 61151, 61153, 61169, 61211, 61223, 61231, 61253, 61261, 61283,
878 61291, 61297, 61331, 61333, 61339, 61343, 61357, 61363, 61379, 61381, 61403,
879 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487, 61493, 61507, 61511,
880 61519, 61543, 61547, 61553, 61559, 61561, 61583, 61603, 61609, 61613, 61627,
881 61631, 61637, 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703, 61717,
882 61723, 61729, 61751, 61757, 61781, 61813, 61819, 61837, 61843, 61861, 61871,
883 61879, 61909, 61927, 61933, 61949, 61961, 61967, 61979, 61981, 61987, 61991,
884 62003, 62011, 62017, 62039, 62047, 62053, 62057, 62071, 62081, 62099, 62119,
885 62129, 62131, 62137, 62141, 62143, 62171, 62189, 62191, 62201, 62207, 62213,
886 62219, 62233, 62273, 62297, 62299, 62303, 62311, 62323, 62327, 62347, 62351,
887 62383, 62401, 62417, 62423, 62459, 62467, 62473, 62477, 62483, 62497, 62501,
888 62507, 62533, 62539, 62549, 62563, 62581, 62591, 62597, 62603, 62617, 62627,
889 62633, 62639, 62653, 62659, 62683, 62687, 62701, 62723, 62731, 62743, 62753,
890 62761, 62773, 62791, 62801, 62819, 62827, 62851, 62861, 62869, 62873, 62897,
891 62903, 62921, 62927, 62929, 62939, 62969, 62971, 62981, 62983, 62987, 62989,
892 63029, 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113, 63127, 63131,
893 63149, 63179, 63197, 63199, 63211, 63241, 63247, 63277, 63281, 63299, 63311,
894 63313, 63317, 63331, 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391,
895 63397, 63409, 63419, 63421, 63439, 63443, 63463, 63467, 63473, 63487, 63493,
896 63499, 63521, 63527, 63533, 63541, 63559, 63577, 63587, 63589, 63599, 63601,
897 63607, 63611, 63617, 63629, 63647, 63649, 63659, 63667, 63671, 63689, 63691,
898 63697, 63703, 63709, 63719, 63727, 63737, 63743, 63761, 63773, 63781, 63793,
899 63799, 63803, 63809, 63823, 63839, 63841, 63853, 63857, 63863, 63901, 63907,
900 63913, 63929, 63949, 63977, 63997, 64007, 64013, 64019, 64033, 64037, 64063,
901 64067, 64081, 64091, 64109, 64123, 64151, 64153, 64157, 64171, 64187, 64189,
902 64217, 64223, 64231, 64237, 64271, 64279, 64283, 64301, 64303, 64319, 64327,
903 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451, 64453, 64483, 64489,
904 64499, 64513, 64553, 64567, 64577, 64579, 64591, 64601, 64609, 64613, 64621,
905 64627, 64633, 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747, 64763,
906 64781, 64783, 64793, 64811, 64817, 64849, 64853, 64871, 64877, 64879, 64891,
907 64901, 64919, 64921, 64927, 64937, 64951, 64969, 64997, 65003, 65011, 65027,
908 65029, 65033, 65053, 65063, 65071, 65089, 65099, 65101, 65111, 65119, 65123,
909 65129, 65141, 65147, 65167, 65171, 65173, 65179, 65183, 65203, 65213, 65239,
910 65257, 65267, 65269, 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371,
911 65381, 65393, 65407, 65413, 65419, 65423, 65437, 65447, 65449, 65479, 65497,
916 * smallest prime > MAX_SM_PRIME (2^32-5) == 2^32+15
919 STATIC CONST HALF _nxt_prime_val_
[] = { 0xf, 0x1 };
920 ZVALUE CONST _nxt_prime_
= { (HALF
*)_nxt_prime_val_
, 2, 0 };
921 NUMBER _nxtprime_
= {{(HALF
*)_nxt_prime_val_
,2,0}, {_oneval_
,1,0}, 1, NULL
};
923 STATIC CONST HALF _nxt_prime_val_
[] = { 0xf, 0x0, 0x1 };
924 ZVALUE CONST _nxt_prime_
= { (HALF
*)_nxt_prime_val_
, 3, 0 };
925 NUMBER _nxtprime_
= {{(HALF
*)_nxt_prime_val_
,3,0}, {_oneval_
,1,0}, 1, NULL
};
929 * JMPMOD*2 as a ZVALUE
931 STATIC CONST HALF _jmpmod2_val_
[] = { JMPMOD
*2 };
932 CONST ZVALUE _jmpmod2_
= { (HALF
*)_jmpmod2_val_
, 1, 0 };
