Primes: n*2^m+1: Difference between revisions

Content added Content deleted
m (A little more specific with the "Stretch harder" goal)
(→‎{{header|ALGOL W}}: Only show 45 primes, in line with the new Task requirements.)
Line 452: Line 452:


=={{header|ALGOL W}}==
=={{header|ALGOL W}}==
Attempts the stretchier stretch goal, however as integers in Algol W are only signed 32 bit, the primes that won't fit in 32 bits are not found.
Although most of the primes up to 500 will fit in 32 bits, obviously 383 won't, having over 6000 digits, so this doesn;t attempt to show more than the first 45. NB: 47 is the first prime that won't fit in 32 bits.
<syntaxhighlight lang="algolw">
<syntaxhighlight lang="algolw">
begin % find primes of the form 1+n*2^m where m is the lowest integer >= 0 %
begin % find primes of the form 1+n*2^m where m is the lowest integer >= 0 %
Line 460: Line 460:
MAX_PRIME := 10000;
MAX_PRIME := 10000;
begin
begin
% returns true if n is prime, false otherwise - uses trial division %
logical procedure isPrime ( integer value n ) ;
if n < 3 then n = 2
else if not odd( n ) then false
else begin
logical prime;
prime := true;
for i := 3 step 2 until entier( sqrt( n ) ) do begin
prime := n rem i not = 0;
if not prime then goto endTest;
end for_i;
endTest: prime
end isPrime ;
logical array prime ( 1 :: MAX_PRIME );
logical array prime ( 1 :: MAX_PRIME );
% sieve the primes to MAX_PRIME %
% sieve the primes to MAX_PRIME %
Line 483: Line 470:
end for_i ;
end for_i ;
% find the n*2^m + 1 primes %
% find the n*2^m + 1 primes %
for n := 1 until 400 do begin
for n := 1 until 45 do begin
integer m, twoToM, p;
integer m, twoToM, p;
logical notFound;
logical notFound;
Line 492: Line 479:
while notFound and m <= MAX_M do begin
while notFound and m <= MAX_M do begin
p := ( n * twoToM ) + 1;
p := ( n * twoToM ) + 1;
notFound := not ( if p > MAX_PRIME then isPrime( p ) else prime( p ) );
notFound := not prime( p );
if notFound then begin
if notFound then begin
twoToM := twoToM + twoToM;
twoToM := twoToM + twoToM;
Line 499: Line 486:
end while_notFound_and_m_le_MAX_M ;
end while_notFound_and_m_le_MAX_M ;
if notFound
if notFound
then write( i_w := 3, s_w := 0, n, " not found" )
then writeon( i_w := 3, s_w := 0, "(", n, " not found)" )
else write( i_w := 3, s_w := 0, n, " ", i_w := 2, m, ": ", i_w := 10, p )
else writeon( i_w := 3, s_w := 0, "(", n, " ", i_w := 1, m, ": ", i_w := 4, p, " )" );
if n rem 5 = 0 then write()
end for_n
end for_n
end
end
Line 506: Line 494:
</syntaxhighlight>
</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre style="height:20ex;overflow:scroll;overflow-wrap;normal;word-wrap:normal;white-space:pre;">
1 0: 2
( 1 0: 2 )( 2 0: 3 )( 3 1: 7 )( 4 0: 5 )( 5 1: 11 )
2 0: 3
( 6 0: 7 )( 7 2: 29 )( 8 1: 17 )( 9 1: 19 )( 10 0: 11 )
3 1: 7
( 11 1: 23 )( 12 0: 13 )( 13 2: 53 )( 14 1: 29 )( 15 1: 31 )
4 0: 5
( 16 0: 17 )( 17 3: 137 )( 18 0: 19 )( 19 6: 1217 )( 20 1: 41 )
( 21 1: 43 )( 22 0: 23 )( 23 1: 47 )( 24 2: 97 )( 25 2: 101 )
5 1: 11
6 0: 7
( 26 1: 53 )( 27 2: 109 )( 28 0: 29 )( 29 1: 59 )( 30 0: 31 )
( 31 8: 7937 )( 32 3: 257 )( 33 1: 67 )( 34 2: 137 )( 35 1: 71 )
7 2: 29
( 36 0: 37 )( 37 2: 149 )( 38 5: 1217 )( 39 1: 79 )( 40 0: 41 )
8 1: 17
( 41 1: 83 )( 42 0: 43 )( 43 2: 173 )( 44 1: 89 )( 45 2: 181 )
9 1: 19
10 0: 11
11 1: 23
12 0: 13
13 2: 53
14 1: 29
15 1: 31
16 0: 17
17 3: 137
18 0: 19
19 6: 1217
20 1: 41
21 1: 43
22 0: 23
23 1: 47
24 2: 97
25 2: 101
26 1: 53
27 2: 109
28 0: 29
29 1: 59
30 0: 31
31 8: 7937
32 3: 257
33 1: 67
34 2: 137
35 1: 71
36 0: 37
37 2: 149
38 5: 1217
39 1: 79
40 0: 41
41 1: 83
42 0: 43
43 2: 173
44 1: 89
45 2: 181
46 0: 47
47 not found
48 1: 97
49 2: 197
50 1: 101
51 1: 103
52 0: 53
53 1: 107
54 1: 109
55 4: 881
56 1: 113
57 2: 229
58 0: 59
59 5: 1889
60 0: 61
61 4: 977
62 7: 7937
63 1: 127
64 2: 257
65 1: 131
66 0: 67
67 2: 269
68 1: 137
69 1: 139
70 0: 71
71 3: 569
72 0: 73
73 2: 293
74 1: 149
75 1: 151
76 4: 1217
77 3: 617
78 0: 79
79 2: 317
80 3: 641
81 1: 163
82 0: 83
83 1: 167
84 2: 337
85 4: 1361
86 1: 173
87 2: 349
88 0: 89
89 1: 179
90 1: 181
91 8: 23297
92 7: 11777
93 2: 373
94 not found
95 1: 191
96 0: 97
97 2: 389
98 1: 197
99 1: 199
100 0: 101
101 3: 809
102 0: 103
103 16: 6750209
104 5: 3329
105 1: 211
106 0: 107
107 3: 857
108 0: 109
109 6: 6977
110 3: 881
111 1: 223
112 0: 113
113 1: 227
114 1: 229
115 2: 461
116 1: 233
117 3: 937
118 4: 1889
119 1: 239
120 1: 241
121 8: 30977
122 3: 977
123 6: 7873
124 6: 7937
125 1: 251
126 0: 127
127 2: 509
128 1: 257
129 3: 1033
130 0: 131
131 1: 263
132 4: 2113
133 4: 2129
134 1: 269
135 1: 271
136 0: 137
137 3: 1097
138 0: 139
139 2: 557
140 1: 281
141 1: 283
142 2: 569
143 not found
144 2: 577
145 6: 9281
146 1: 293
147 8: 37633
148 0: 149
149 3: 1193
150 0: 151
151 4: 2417
152 3: 1217
153 1: 307
154 2: 617
155 1: 311
156 0: 157
157 8: 40193
158 1: 317
159 6: 10177
160 2: 641
161 3: 1289
162 0: 163
163 2: 653
164 9: 83969
165 1: 331
166 0: 167
167 7: 21377
168 1: 337
169 2: 677
170 3: 1361
171 8: 43777
172 0: 173
173 1: 347
174 1: 349
175 2: 701
176 1: 353
177 2: 709
178 0: 179
179 1: 359
180 0: 181
181 4: 2897
182 7: 23297
183 1: 367
184 6: 11777
185 3: 1481
186 1: 373
187 6: 11969
188 not found
189 1: 379
190 0: 191
191 1: 383
192 0: 193
193 2: 773
194 1: 389
195 4: 3121
196 0: 197
197 15: 6455297
198 0: 199
199 2: 797
200 1: 401
201 3: 1609
202 2: 809
203 13: 1662977
204 1: 409
205 2: 821
206 15: 6750209
207 2: 829
208 4: 3329
209 1: 419
210 0: 211
211 20: 221249537
212 3: 1697
213 2: 853
214 2: 857
215 1: 431
216 1: 433
217 not found
218 5: 6977
219 1: 439
220 2: 881
221 1: 443
222 0: 223
223 8: 57089
224 1: 449
225 3: 1801
226 0: 227
227 11: 464897
228 0: 229
229 6: 14657
230 1: 461
231 1: 463
232 0: 233
233 1: 467
234 2: 937
235 2: 941
236 3: 1889
237 4: 3793
238 0: 239
239 1: 479
240 0: 241
241 not found
242 7: 30977
243 1: 487
244 2: 977
245 1: 491
246 5: 7873
247 6: 15809
248 5: 7937
249 1: 499
250 0: 251
251 1: 503
252 2: 1009
253 2: 1013
254 1: 509
255 2: 1021
256 0: 257
257 not found
258 2: 1033
259 not found
260 1: 521
261 1: 523
262 0: 263
263 not found
264 3: 2113
265 2: 1061
266 3: 2129
267 2: 1069
268 0: 269
269 3: 2153
270 0: 271
271 4: 4337
272 11: 557057
273 1: 547
274 2: 1097
275 7: 35201
276 0: 277
277 2: 1109
278 1: 557
279 2: 1117
280 0: 281
281 1: 563
282 0: 283
283 not found
284 1: 569
285 1: 571
286 not found
287 3: 2297
288 1: 577
289 10: 295937
290 5: 9281
291 4: 4657
292 0: 293
293 1: 587
294 7: 37633
295 2: 1181
296 1: 593
297 3: 2377
298 2: 1193
299 1: 599
300 1: 601
301 4: 4817
302 3: 2417
303 1: 607
304 2: 1217
305 3: 2441
306 0: 307
307 2: 1229
308 1: 617
309 1: 619
310 0: 311
311 9: 159233
312 0: 313
313 4: 5009
314 7: 40193
315 1: 631
316 0: 317
317 7: 40577
318 5: 10177
319 2: 1277
320 1: 641
321 1: 643
322 2: 1289
323 1: 647
324 2: 1297
325 2: 1301
326 1: 653
327 3: 2617
328 8: 83969
329 1: 659
330 0: 331
331 4: 5297
332 3: 2657
333 5: 10657
334 6: 21377
335 19: 175636481
336 0: 337
337 4: 5393
338 1: 677
339 3: 2713
340 2: 1361
341 1: 683
342 7: 43777
343 2: 1373
344 3: 2753
345 1: 691
346 0: 347
347 3: 2777
348 0: 349
349 10: 357377
350 1: 701
351 12: 1437697
352 0: 353
353 21: 740294657
354 1: 709
355 6: 22721
356 5: 11393
357 2: 1429
358 0: 359
359 1: 719
360 6: 23041
361 not found
362 3: 2897
363 1: 727
364 6: 23297
365 5: 11681
366 0: 367
367 12: 1503233
368 5: 11777
369 1: 739
370 2: 1481
371 1: 743
372 0: 373
373 2: 1493
374 5: 11969
375 1: 751
376 not found
377 11: 772097
378 0: 379
379 14: 6209537
380 1: 761
381 3: 3049
382 0: 383
383 not found
384 1: 769
385 8: 98561
386 1: 773
387 2: 1549
388 0: 389
389 11: 796673
390 3: 3121
391 4: 6257
392 3: 3137
393 1: 787
394 14: 6455297
395 5: 12641
396 0: 397
397 4: 6353
398 1: 797
399 2: 1597
400 0: 401
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Primes:_n*2%5Em%2B1"