Penta-power prime seeds: Difference between revisions
Added Algol 68
(→{{header|Wren}}: n must be odd - thanks to Tigerofdarkness for pointing that out.) |
(Added Algol 68) |
||
Line 20:
<br>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 3.0.3 under Windows}}
This uses ALGOL 68G's LONG LONG INT during the Miller Rabin testing, under ALGOL 68G version three, the default precision of LONG LONG INT is 72 digits and LONG INT is 128 bit.<br>
A sieve is used to (hopefully) quickly eliminate non-prime n+2 and 2n+1 numbers - Millar Rabin is used for n^2+n+1 etc. that are larger than the sieve.
<br>
This is about 10 times faster than the equivalent Quad-powwr prime seed program, possibly because even numbers are excluded and the n+2 test eliminates more numbers before the higher powers must be calculated..
{{libheader|ALGOL 68-primes}}
NB: The source of the ALGOL 68-primes library is on a Rosetta Code code page linked from the above.
<lang algol68>BEGIN # find some Penta power prime seeds, numbers n such that: #
# n^p + n + 1 is prime for p = 0. 1, 2, 3, 4 #
PR read "primes.incl.a68" PR # include prime utilities #
INT max prime = 22 000 000;
# sieve the primes to max prime - 22 000 000 should be enough to allow #
# checking primality of 2n+1 up to a little under 11 000 000 which should #
# be enough for the task #
[ 0 : max prime ]BOOL prime;
FOR i FROM LWB prime TO UPB prime DO prime[ i ] := FALSE OD;
prime[ 0 ] := prime[ 1 ] := FALSE;
prime[ 2 ] := TRUE;
FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE OD;
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO
IF prime[ i ] THEN
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD
FI
OD;
# returns TRUE if p is (probably) prime, FALSE otherwise #
# uses the sieve if possible, Miller Rabin otherwise #
PROC is prime = ( LONG INT p )BOOL:
IF p <= max prime
THEN prime[ SHORTEN p ]
ELSE is probably prime( p )
FI;
# attempt to find the numbers, note n^0 + n + 1 = n + 2 so n must be odd #
BOOL finished := FALSE;
INT count := 0;
INT next limit := 1 000 000;
INT limit increment = next limit;
[ 10 ]INT first, limit, index;
INT l count := 0;
print( ( "First 30 Penta power prime seeds:", newline ) );
FOR n BY 2 WHILE NOT finished DO
IF prime[ n + 2 ] THEN
IF INT n1 = n + 1;
prime[ n + n1 ]
THEN
# n^0 + n + 1 and n^1 + n + 1 are prime #
LONG INT np := n * n;
IF is prime( np + n1 ) THEN
# n^2 + n + 1 is prime #
IF is prime( ( np *:= n ) + n1 ) THEN
# n^3 + n + 1 is prime #
IF is prime( ( np * n ) + n1 ) THEN
# n^4 + n + 1 is prime - have a suitable number #
count +:= 1;
IF n > next limit THEN
# found the first element over the next limit #
first[ l count +:= 1 ] := n;
limit[ l count ] := next limit;
index[ l count ] := count;
next limit +:= limit increment;
finished := l count >= UPB first
FI;
IF count <= 30 THEN
# found one of the first 30 numbers #
print( ( " ", whole( n, -8 ) ) );
IF count MOD 10 = 0 THEN print( ( newline ) ) FI
FI
FI
FI
FI
FI
FI
OD;
print( ( newline ) );
FOR i TO UPB first DO
print( ( "First element over ", whole( limit[ i ], -10 )
, ": ", whole( first[ i ], -10 )
, ", index: ", whole( index[ i ], -6 )
, newline
)
)
OD
END</lang>
{{out}}
<pre>
First 30 Penta power prime seeds:
1 5 69 1665 2129 25739 29631 62321 77685 80535
82655 126489 207285 211091 234359 256719 366675 407945 414099 628859
644399 770531 781109 782781 923405 1121189 1158975 1483691 1490475 1512321
First element over 1000000: 1121189, index: 26
First element over 2000000: 2066079, index: 39
First element over 3000000: 3127011, index: 47
First element over 4000000: 4059525, index: 51
First element over 5000000: 5279175, index: 59
First element over 6000000: 6320601, index: 63
First element over 7000000: 7291361, index: 68
First element over 8000000: 8334915, index: 69
First element over 9000000: 9100671, index: 71
First element over 10000000: 10347035, index: 72
</pre>
=={{header|Raku}}==
<lang perl6>use Lingua::EN::Numbers;
| |||