Primes: n*2^m+1: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: use pygments) |
(Added Oberon-07) |
||
Line 1,654: | Line 1,654: | ||
{{out}} |
{{out}} |
||
<pre style="height:12ex;overflow:scroll; |
<pre style="height:12ex;overflow:scroll;"> n m prime |
||
1 0 2 |
1 0 2 |
||
2 0 3 |
2 0 3 |
||
Line 2,126: | Line 2,126: | ||
399 2 1597 |
399 2 1597 |
||
400 0 401 |
400 0 401 |
||
</pre> |
|||
=={{header|Oberon-07}}== |
|||
<syntaxhighlight lang="modula2"> |
|||
(* find primes of the form 1+n*2^m *) |
|||
(* where m is the lowest integer >= 0 such that 1+n*2^m is prime *) |
|||
MODULE primesNx2ToMPlus1; |
|||
IMPORT |
|||
Math, Out; |
|||
CONST |
|||
MaxM = 22; (* maximum m we will consider *) |
|||
MaxPrime = 10000; (* sieve size *) |
|||
VAR prime :ARRAY MaxPrime + 1 OF BOOLEAN; |
|||
PROCEDURE Sieve; (* Sieve the primes to MaxPrime *) |
|||
VAR i, ii, pr :INTEGER; |
|||
BEGIN |
|||
prime[ 0 ] := FALSE; prime[ 1 ] := FALSE; prime[ 2 ] := TRUE; |
|||
FOR i := 4 TO MaxPrime BY 2 DO prime[ i ] := FALSE END; |
|||
FOR i := 3 TO MaxPrime BY 2 DO prime[ i ] := TRUE END; |
|||
FOR i := 3 TO FLOOR( Math.sqrt( FLT( MaxPrime ) ) ) BY 2 DO |
|||
IF prime[ i ] THEN |
|||
ii := i + i; |
|||
pr := i * i; |
|||
WHILE pr <= MaxPrime DO |
|||
prime[ pr ] := FALSE; |
|||
pr := pr + ii |
|||
END |
|||
END |
|||
END |
|||
END Sieve; |
|||
PROCEDURE ShowPrimes; (* find the n*2^m + 1 primes *) |
|||
VAR n, m, nx2ToM, p :INTEGER; |
|||
found :BOOLEAN; |
|||
BEGIN |
|||
FOR n := 1 TO 45 DO |
|||
m := 0; |
|||
nx2ToM := n; |
|||
p := 0; |
|||
found := FALSE; |
|||
WHILE ~ found & ( m <= MaxM ) DO |
|||
p := nx2ToM + 1; |
|||
found := prime[ p ]; |
|||
IF ~ found THEN |
|||
nx2ToM := nx2ToM + nx2ToM; |
|||
m := m + 1 |
|||
END |
|||
END; |
|||
Out.Int( n, 3 ); |
|||
IF ~ found THEN |
|||
Out.String( " not found)" ) |
|||
ELSE |
|||
Out.Int( m, 4 );Out.String( ": " );Out.Int( p, 0 ) |
|||
END; |
|||
Out.Ln |
|||
END |
|||
END ShowPrimes; |
|||
BEGIN |
|||
Sieve; |
|||
ShowPrimes; |
|||
END primesNx2ToMPlus1. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre style="height:12ex;overflow:scroll;"> |
|||
1 0: 2 |
|||
2 0: 3 |
|||
3 1: 7 |
|||
4 0: 5 |
|||
5 1: 11 |
|||
6 0: 7 |
|||
7 2: 29 |
|||
8 1: 17 |
|||
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 |
|||
</pre> |
</pre> |
||