Primes: n*2^m+1: Difference between revisions
Added Oberon-07
m (→{{header|Phix}}: use pygments) |
(Added Oberon-07) |
||
Line 1,654:
{{out}}
<pre style="height:12ex;overflow:scroll;
1 0 2
2 0 3
Line 2,126:
399 2 1597
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>
| |||