Wagstaff primes: Difference between revisions
Added Algol 68
Thundergnat (talk | contribs) m (→{{header|Raku}}: Restore accidentally deleted Wren header) |
(Added Algol 68) |
||
Line 19:
* [[oeis:A000979|OEIS:A000979 - Wagstaff primes]]
<br><br>
=={{header|ALGOL 68}}==
Basic task - assumes LONG INT is 64 bit.
<syntaxhighlight lang="algol68">
BEGIN # find some Wagstaff primes: primes of the form ( 2^p + 1 ) / 3 #
# where p is an odd prime #
INT max wagstaff = 10; # number of Wagstaff primes to find #
INT w count := 0; # numbdr of Wagstaff primes found so far #
# sieve the primes up to 200, hopefully enough... #
[ 0 : 200 ]BOOL primes;
primes[ 0 ] := primes[ 1 ] := FALSE;
primes[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB primes DO primes[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB primes DO primes[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB primes ) DO
IF primes[ i ] THEN
FOR s FROM i * i BY i + i TO UPB primes DO primes[ s ] := FALSE OD
FI
OD;
# attempt to find the Wagstaff primes #
LONG INT power of 2 := 2; # 2^1 #
FOR p FROM 3 BY 2 WHILE w count < max wagstaff DO
power of 2 *:= 4;
IF primes[ p ] THEN
LONG INT w := ( power of 2 + 1 ) OVER 3;
# check w is prime - trial division #
BOOL is prime := TRUE;
LONG INT n := 3;
WHILE n * n <= w AND is prime DO
is prime := w MOD n /= 0;
n +:= 2
OD;
IF is prime THEN
# have another Wagstaff prime #
w count +:= 1;
print( ( whole( w count, -2 )
, ": "
, whole( p, -4 )
, ": "
, whole( w, 0 )
, newline
)
)
FI
FI
OD
END
</syntaxhighlight>
{{out}}
<pre>
1: 3: 3
2: 5: 11
3: 7: 43
4: 11: 683
5: 13: 2731
6: 17: 43691
7: 19: 174763
8: 23: 2796203
9: 31: 715827883
10: 43: 2932031007403
</pre>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line># First 20
| |||